論文

査読有り
2005年1月

Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs

DISCRETE APPLIED MATHEMATICS
  • R Uehara
  • ,
  • S Toda
  • ,
  • T Nagoya

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.

リンク情報
DOI
https://doi.org/10.1016/j.dam.2004.06.008
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000226452800015&DestApp=WOS_CPL
ID情報
  • DOI : 10.1016/j.dam.2004.06.008
  • ISSN : 0166-218X
  • eISSN : 1872-6771
  • Web of Science ID : WOS:000226452800015

エクスポート
BibTeX RIS