The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
From MaRDI portal
Publication:1959391
DOI10.1007/s00224-009-9188-4zbMath1203.05104MaRDI QIDQ1959391
Fabian Wagner, Thomas Thierauf
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/
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
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
