On the Proper-Path-Decomposition of Trees

Atsushi TAKAHASHI  Shuichi UENO  Yoji KAJITANI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.1   pp.131-136
Publication Date: 1995/01/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Graphs, Networks and Matroids
proper-path-width,  proper-path-decomposition,  path-width,  path-decomposition,  polynomial time algorithm,  

Full Text: PDF>>
Buy this Article

We introduce the interval set of a graph G which is a representation of the proper-path-decomposition of G, and show a linear time algorithm to construct an optimal interval set for any tree T. It is shown that a proper-path-decomposition of T with optimal width can be obtained from an optimal interval set of T in O(n log n) time.