Completeness results for graph isomorphism.
From MaRDI portal
Publication:1401960
DOI10.1016/S0022-0000(03)00042-4zbMath1054.68101OpenAlexW2006771561MaRDI QIDQ1401960
Johannes Köbler, Birgit Jenner, Pierre McKenzie, Jacobo Toran
Publication date: 19 August 2003
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(03)00042-4
Related Items (18)
Compressed Tree Canonization ⋮ The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ The parallel complexity of graph canonization under abelian group action ⋮ A Logspace Algorithm for Partial 2-Tree Canonization ⋮ The isomorphism problem for planar 3-connected graphs is in unambiguous logspace ⋮ The Space Complexity of k-Tree Isomorphism ⋮ Isomorphism of Regular Trees and Words ⋮ Colored hypergraph isomorphism is fixed parameter tractable ⋮ Unnamed Item ⋮ Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Restricted space algorithms for isomorphism on bounded treewidth graphs ⋮ Reductions to graph isomorphism ⋮ Reductions to Graph Isomorphism ⋮ Solution-Graphs of Boolean Formulas and Isomorphism ⋮ On the Complexity of Matroid Isomorphism Problems ⋮ Solution-Graphs of Boolean Formulas and Isomorphism1 ⋮ On the isomorphism problem for decision trees and decision lists
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Symmetric space-bounded computation
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- An optimal lower bound on the number of variables for graph identification
- Circuits, matrices, and nonassociative computation
- \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs
- On uniformity within \(NC^ 1\)
- Problems complete for deterministic logarithmic space
- Parallel Tree Contraction Part 2: Further Applications
- On computing Boolean connectives of characteristic functions
This page was built for publication: Completeness results for graph isomorphism.