Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.

DOI10.4230/LIPIcs.FSTTCS.2009.2314zbMath1248.68239OpenAlexW2022507120MaRDI QIDQ2920122

Samir Datta, Prajakta Nimbhorkar, Fabian Wagner, Thomas Thierauf

Publication date: 24 October 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_1142.html

zbMATH Keywords

graph isomorphism\(K_{3\(K_5\)-free graphs3}\)-free graphsLog-space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (10)

A Fourier-theoretic approach for inferring symmetries ⋮ On the complexity of matroid isomorphism problem ⋮ Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$ ⋮ Counting the number of perfect matchings in \(K_{5}\)-free graphs ⋮ Some Tractable Win-Lose Games ⋮ Planarity Testing Revisited ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Restricted space algorithms for isomorphism on bounded treewidth graphs ⋮ Unnamed Item ⋮ Revising Johnson's table for the 21st century

This page was built for publication: Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.