Polynomial isomorphism algorithm for graphs which do not pinch to \(K_{3,g}\)

DOI10.1007/BF01095641zbMath0595.68057MaRDI QIDQ1077933

Ilya Nikolaevich Ponomarenko

Publication date: 1986

Published in: Journal of Soviet Mathematics (Search for Journal in Brave)

zbMATH Keywords

polynomial-time algorithmtime complexitygraph isomorphismundirected graphsgraphs of bounded valence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Related Items (1)

Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract)

Cites Work

• Isomorphism of graphs of bounded valence can be tested in polynomial time
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Groups of graphs on given surfaces

This page was built for publication: Polynomial isomorphism algorithm for graphs which do not pinch to \(K_{3,g}\)