For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On the Proper-Path-Decomposition of Trees
Atsushi TAKAHASHI Shuichi UENO Yoji KAJITANI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1995/01/25
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>>
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.