Computational Complexity of Graph Isomorphism Problem(<特集>Special Issue on Selected Papers from LA Symposium)

スポンサーリンク

概要

• 論文の詳細を見る

• In this article, we give a survey on the computational complexity of the Graph Isomorphism Problem (GI for short). We first discuss two major evidences by which we may expect GI not to be NP-hard. We next explore the computational complexity of GI for many subclasses of the graphs. We then give a sketchy outline of two polynomial-time algorithms: Luks's algorithm for trivalent graphs and Nagoya's algorithm for chordal graphs with bounded clique number.

• 社団法人電子情報通信学会の論文
• 2002-02-01

著者

• Toda Seinosuke

  College Of Humanities And Sciences Nihon University

関連論文

• Computational Complexity of Graph Isomorphism Problem(Special Issue on Selected Papers from LA Symposium)

スポンサーリンク