A polynomial algorithm for finding T-span of generalized cacti

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 Delta less than or equal to 3 and it is polynomially solvable for graphs with degree Delta less than or equal to 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. (C) 2003 Elsevier B.V. All rights reserved.