Completeness results for graph isomorphism.
From MaRDI portal
Publication:1401960
Recommendations
Cites work
- A\,V^ 2 algorithm for determining isomorphism of planar graphs
- An optimal lower bound on the number of variables for graph identification
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Circuits, matrices, and nonassociative computation
- scientific article; zbMATH DE number 440476 (Why is no real title available?)
- scientific article; zbMATH DE number 3723875 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 1263189 (Why is no real title available?)
- scientific article; zbMATH DE number 1335884 (Why is no real title available?)
- scientific article; zbMATH DE number 477971 (Why is no real title available?)
- scientific article; zbMATH DE number 1088188 (Why is no real title available?)
- scientific article; zbMATH DE number 2086379 (Why is no real title available?)
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- On computing Boolean connectives of characteristic functions
- On uniformity within \(NC^ 1\)
- Parallel Tree Contraction Part 2: Further Applications
- Problems complete for deterministic logarithmic space
- Symmetric space-bounded computation
Cited in
(29)- Computing complete graph isomorphisms and Hamiltonian cycles from partial ones
- Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
- Isomorphism certificates for undirected graphs
- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- Colored hypergraph isomorphism is fixed parameter tractable
- On the isomorphism problem for decision trees and decision lists
- Corrigendum to ``Completeness results for graph isomorphism
- Solution-Graphs of Boolean Formulas and Isomorphism
- Isomorphism of regular trees and words
- The Isomorphism Problem for k-Trees Is Complete for Logspace
- On the Complexity of Matroid Isomorphism Problems
- Compressed tree canonization
- scientific article; zbMATH DE number 4156494 (Why is no real title available?)
- A Logspace Algorithm for Partial 2-Tree Canonization
- The parallel complexity of graph canonization under abelian group action
- scientific article; zbMATH DE number 6970796 (Why is no real title available?)
- scientific article; zbMATH DE number 2086379 (Why is no real title available?)
- Solution-Graphs of Boolean Formulas and Isomorphism1
- Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
- The Space Complexity of k-Tree Isomorphism
- Graph isomorphism completeness for perfect graphs and subclasses of perfect graphs
- Reductions to Graph Isomorphism
- Logical Approaches to Computational Barriers
- Graph isomorphism restricted by lists
- Count-free Weisfeiler-Leman and group isomorphism
- On the parallel complexity of group isomorphism via Weisfeiler-Leman
- The isomorphism problem for \(k\)-trees is complete for logspace
- Restricted space algorithms for isomorphism on bounded treewidth graphs
- Reductions to graph isomorphism
This page was built for publication: Completeness results for graph isomorphism.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401960)
