Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Special Session Talk:
Complexity of Graph Isomorphism for Restricted Graph Classes

Speaker: Johannes Köbler
Presentation: v-gi-cie.pdf

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.

websites: Arnold Beckmann 2006-04-21 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net