2005年1月
Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
DISCRETE APPLIED MATHEMATICS
- ,
- ,
- 巻
- 145
- 号
- 3
- 開始ページ
- 479
- 終了ページ
- 482
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.dam.2004.06.008
- 出版者・発行元
- ELSEVIER SCIENCE BV
This paper deals with the graph isomorphism (GI) problem for two graph classes: chordal bipartite graphs and strongly chordal graphs. It is known that GI problem is GI complete even for some special graph classes including regular graphs, bipartite graphs, chordal graphs, comparability graphs, split graphs, and k-trees with unbounded k. On the other hand, the relative complexity of the GI problem for the above classes was unknown. We prove that deciding isomorphism of the classes are GI complete. (C) 2004 Elsevier B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.dam.2004.06.008
- ISSN : 0166-218X
- eISSN : 1872-6771
- Web of Science ID : WOS:000226452800015