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

DOI10.1007/BF01095641MaRDI QIDQ1077933zbMATH OpenFDO

Authors Ilya Ponomarenko

Publication date 1986

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

Full work available at URL https://doi.org/10.1007/BF01095641

zbMATH Keywords

graph isomorphismgraphs of bounded valencepolynomial-time algorithmtime complexityundirected graphs

Mathematics Subject Classification ID

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

Review text

Translation from Zap. Nauchn. Semin. Leningr. Otd. Mat. Inst. Steklova 137, 99-114 (Russian) (1984; Zbl 0551.68060).

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)