The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
From MaRDI portal
Publication:1959391
DOI10.1007/s00224-009-9188-4zbMath1203.05104OpenAlexW2019136393MaRDI QIDQ1959391
Thomas Thierauf, Fabian Wagner
Publication date: 6 October 2010
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1327/
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (4)
Depth-first search in directed planar graphs, revisited ⋮ On the power of unambiguity in log-space ⋮ A Logspace Algorithm for Partial 2-Tree Canonization ⋮ Frameworks for designing in-place graph algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The method of forced enumeration for nondeterministic automata
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Planarity testing in parallel
- Completeness results for graph isomorphism.
- Universal traversal sequences with backtracking.
- Directed Planar Reachability Is in Unambiguous Log-Space
- Algorithm and Experiments in Testing Planar Graphs for Isomorphism
- A Logspace Algorithm for Partial 2-Tree Canonization
- Hardness Results for Tournament Isomorphism and Automorphism
- Undirected ST-connectivity in log-space
- Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
- Testing Graph Isomorphism in Parallel by Playing a Game
- A taxonomy of problems with fast parallel algorithms
- Nondeterministic Space is Closed under Complementation
- Parallel Tree Contraction Part 2: Further Applications
- Efficient Planarity Testing
- On the Hardness of Graph Isomorphism
- A Set of Topological Invariants for Graphs
- Making Nondeterminism Unambiguous
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
This page was built for publication: The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
