On the Minimum Tree Representation of Chordal Graphs
Summary :
An algorithm is proposed to obtain minimum tree representation of a chordal graph on an algorithm obtained in Ref.(5), and we prove that any tree obtained by this algorithm is optimal for two kinds of optimization problems, that is 1) to obtain a clique tree with the minimum sum of weights on edges and 2) to obtain a clique tree with the minimum sum of weights of subtrees corresponding to vertices.
- Publication
- IEICE TRANSACTIONS on transactions Vol.E71-E No.3 pp.203-204
- Publication Date
- 1988/03/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- LETTER
- Category
- Graphs and Networks
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
Yukio SHIBATA, Akiko ISHIJIMA, "On the Minimum Tree Representation of Chordal Graphs" in IEICE TRANSACTIONS on transactions,
vol. E71-E, no. 3, pp. 203-204, March 1988, doi: .
Abstract: An algorithm is proposed to obtain minimum tree representation of a chordal graph on an algorithm obtained in Ref.(5), and we prove that any tree obtained by this algorithm is optimal for two kinds of optimization problems, that is 1) to obtain a clique tree with the minimum sum of weights on edges and 2) to obtain a clique tree with the minimum sum of weights of subtrees corresponding to vertices.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e71-e_3_203/_p
Copy
@ARTICLE{e71-e_3_203,
author={Yukio SHIBATA, Akiko ISHIJIMA, },
journal={IEICE TRANSACTIONS on transactions},
title={On the Minimum Tree Representation of Chordal Graphs},
year={1988},
volume={E71-E},
number={3},
pages={203-204},
abstract={An algorithm is proposed to obtain minimum tree representation of a chordal graph on an algorithm obtained in Ref.(5), and we prove that any tree obtained by this algorithm is optimal for two kinds of optimization problems, that is 1) to obtain a clique tree with the minimum sum of weights on edges and 2) to obtain a clique tree with the minimum sum of weights of subtrees corresponding to vertices.},
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - On the Minimum Tree Representation of Chordal Graphs
T2 - IEICE TRANSACTIONS on transactions
SP - 203
EP - 204
AU - Yukio SHIBATA
AU - Akiko ISHIJIMA
PY - 1988
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E71-E
IS - 3
JA - IEICE TRANSACTIONS on transactions
Y1 - March 1988
AB - An algorithm is proposed to obtain minimum tree representation of a chordal graph on an algorithm obtained in Ref.(5), and we prove that any tree obtained by this algorithm is optimal for two kinds of optimization problems, that is 1) to obtain a clique tree with the minimum sum of weights on edges and 2) to obtain a clique tree with the minimum sum of weights of subtrees corresponding to vertices.
ER -
English
