Paper Info
Title
On graph isomorphism for restricted graph classes
Abstract
Graph isomorphism (GI) is one of the few remaining problems in NP whose complexity status couldn't be solved by classifying it as being either NP-complete or solvable in P. Nevertheless, efficient (polynomial-time or even NC) algorithms for restricted versions of GI have been found over the last four decades. Depending on the graph class, the design and analysis of algorithms for GI use tools from various fields, such as combinatorics, algebra and logic. In this paper, we collect several complexity results on graph isomorphism testing and related algorithmic problems for restricted graph classes from the literature. Further, we provide some new complexity bounds (as well as easier proofs of some known results) and highlight some open questions.
Year
DOI
Venue
2006
10.1007/11780342_26
CiE
Keywords
DocType
Volume
graph isomorphism,gi use tool,restricted graph class,complexity result,new complexity bound,restricted version,graph class,easier proof,complexity status,graph isomorphism testing,polynomial time
Conference
3988
ISSN
ISBN
Citations 
0302-9743
3-540-35466-2
14
PageRank 
References 
Authors
0.63
38
1
Name
Order
Citations
PageRank
Johannes Köbler158046.51