Completeness results for graph isomorphism.

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

zbMATH Keywords

upper boundsgraph automorphism problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

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.