Graph isomorphism for K₃,3-free and K₅-free graphs is in Log-space
DOI10.4230/LIPICS.FSTTCS.2009.2314zbMATH Open1248.68239OpenAlexW2022507120MaRDI QIDQ2920122FDOQ2920122
Authors: Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner 
Publication date: 24 October 2012
Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_1142.html
Recommendations
- Isomorphism Testing for Graphs Excluding Small Minors
- The isomorphism problem for \(k\)-trees is complete for logspace
- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- 3-connected Planar Graph Isomorphism is in Log-space
- Reachability in \(K_{3,3}\)-free and \(K_5\)-free graphs is in unambiguous logspace
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cited In (15)
- 3-connected Planar Graph Isomorphism is in Log-space
- Restricted space algorithms for isomorphism on bounded treewidth graphs
- The isomorphism problem for \(k\)-trees is complete for logspace
- Some tractable win-lose games
- Title not available (Why is that?)
- Graphs of bounded treewidth can be canonized in AC\(^1\)
- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- Title not available (Why is that?)
- On the complexity of matroid isomorphism problem
- Faster isomorphism for \(p\)-groups of class 2 and exponent \(p\)
- Counting the number of perfect matchings in \(K_{5}\)-free graphs
- Planarity testing revisited
- Count-free Weisfeiler-Leman and group isomorphism
- Revising Johnson's table for the 21st century
- A Fourier-theoretic approach for inferring symmetries
This page was built for publication: Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2920122)
