A linear time algorithm for isomorphism of graphs of bounded average genus Conference Paper uri icon

abstract

  • Springer-Verlag Berlin Heidelberg 1993. Recent progress in topological graph theory has shown potential applicability of average genus to graph isomorphism testing. The present paper describes an initial effort at combining topological invariants with combinatorial analysis to design efficient graph isomorphism algorithms. In particular, a linear time algorithm for isomorphism of graphs of bounded average genus is presented.

name of conference

  • Graph-Theoretic Concepts in Computer Science, 18th International Workshop, WG '92, Wiesbaden-Naurod, Germany, June 19-20, 1992, Proceedings

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Chen, J.

complete list of authors

  • Chen, J

publication date

  • January 1993