Polynomial isomorphism algorithm for graphs which do not pinch to K₃,g

DOI10.1007/BF01095641zbMATH Open0595.68057MaRDI QIDQ1077933FDOQ1077933

Authors: Ilya Ponomarenko 

Publication date: 1986

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

zbMATH Keywords

graph isomorphismpolynomial-time algorithmundirected graphstime complexitygraphs 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)

Cites Work

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

Cited In (1)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1077933)