𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A polynomial algorithm for finding T-span of generalized cacti

✍ Scribed by Krzysztof Giaro; Robert Janczewski; Michał Małafiejski

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
166 KB
Volume
129
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

It has been known for years that the problem of computing the T -span is NP-hard in general. Recently, Giaro et al. (Discrete Appl. Math., to appear) showed that the problem remains NP-hard even for graphs of degree 6 3 and it is polynomially solvable for graphs with degree 6 2. Herein, we extend the latter result. We introduce a new class of graphs which is large enough to contain paths, cycles, trees, cacti, polygon trees and connected outerplanar graphs. Next, we study the properties of graphs from this class and prove that the problem of computing the T -span for these graphs is polynomially solvable.

📜 SIMILAR VOLUMES

A generalized algorithm for the recursiv
A generalized algorithm for the recursive implementation of polynomial filters
✍ P. Agathoklis; H. Xu 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 644 KB

Polynomial jilters have many applications in real time control, estimation and identification, particularly when information about the system dynamics and noise statistics are not precisely known. In this paper, a generalized recursive algorithm for nth order polynomial jilters is developed. The par