IEICE TRANSACTIONS on Fundamentals
On the Proper-Path-Decomposition of Trees
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E78-A No.1 pp.131-136
- Publication Date
- 1995/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- LETTER
- Category
- Graphs, Networks and Matroids
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Atsushi TAKAHASHI, Shuichi UENO, Yoji KAJITANI, "On the Proper-Path-Decomposition of Trees" in IEICE TRANSACTIONS on Fundamentals,
vol. E78-A, no. 1, pp. 131-136, January 1995, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e78-a_1_131/_p
Copy
@ARTICLE{e78-a_1_131,
author={Atsushi TAKAHASHI, Shuichi UENO, Yoji KAJITANI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Proper-Path-Decomposition of Trees},
year={1995},
volume={E78-A},
number={1},
pages={131-136},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - On the Proper-Path-Decomposition of Trees
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 131
EP - 136
AU - Atsushi TAKAHASHI
AU - Shuichi UENO
AU - Yoji KAJITANI
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E78-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1995
AB - 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.
ER -
English
