scientific article; zbMATH DE number 477971

Jacobo Toran, Uwe Schoening, Johannes Köbler

Publication date: 8 December 1993

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

graph isomorphism problem structural complexity theory

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. ⋮ Computational aspects of the Gromov-Hausdorff distance and its application in non-rigid shape matching ⋮ Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness ⋮ The complexity of Boolean matrix root computation ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ Linear time algorithms for Abelian group isomorphism and related problems ⋮ Graph isomorphism for graph classes characterized by two forbidden induced subgraphs ⋮ A method for agent-based models validation ⋮ Quantum mechanics on finite groups ⋮ Complexity results in graph reconstruction ⋮ How to define a linear order on finite models ⋮ Practical post-quantum signature schemes from isomorphism problems of trilinear forms ⋮ On distance between graphs ⋮ Zero knowledge and circuit minimization ⋮ The parallel complexity of graph canonization under abelian group action ⋮ Parameterized circuit complexity and the \(W\) hierarchy ⋮ Graph isomorphism, color refinement, and compactness ⋮ Isomorphism testing of read-once functions and polynomials ⋮ Computational complexity of reconstruction and isomorphism testing for designs and line graphs ⋮ A Logspace Algorithm for Partial 2-Tree Canonization ⋮ From Invariants to Canonization in Parallel ⋮ Quantum public-key signature scheme based on asymmetric quantum encryption with trapdoor information ⋮ Polynomial time algorithms for variants of graph matching on partial \(k\)-trees ⋮ An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF ⋮ Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ Towards an isomorphism dichotomy for hereditary graph classes ⋮ Completeness results for graph isomorphism. ⋮ On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two ⋮ Algorithms for highly symmetric linear and integer programs ⋮ Computational indistinguishability between quantum states and its cryptographic application ⋮ G-Tries: a data structure for storing and finding subgraphs ⋮ On the complexity of matroid isomorphism problem ⋮ Containment of conjunctive queries on annotated relations ⋮ The graph isomorphism problem and approximate categories ⋮ The isomorphism problem for planar 3-connected graphs is in unambiguous logspace ⋮ On complete systems of invariants for small graphs ⋮ The complexity of game isomorphism ⋮ Almost complete sets. ⋮ Computational complexity of \(k\)-block conjugacy ⋮ The module isomorphism problem reconsidered. ⋮ Neighborhood hypergraphs of bipartite graphs ⋮ Graph isomorphism and identification matrices: Sequential algorithms ⋮ Promise Problems on Probability Distributions ⋮ Exploring the tractability border in epistemic tasks ⋮ Spectrally Robust Graph Isomorphism ⋮ On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions ⋮ On the acceptance power of regular languages ⋮ Computing functions with parallel queries to NP ⋮ The reachability problem for finite cellular automata ⋮ If NP has polynomial-size circuits, then MA=AM ⋮ A language-dependent cryptographic primitive ⋮ New collapse consequences of NP having small circuits ⋮ On the decidability and complexity of the structural congruence for beta-binders ⋮ On the asymmetric complexity of the group-intersection problem ⋮ Colored hypergraph isomorphism is fixed parameter tractable ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs ⋮ Applications of dimensionality reduction and exponential sums to graph automorphism ⋮ Linear and sublinear time algorithms for the basis of abelian groups ⋮ Graph Isomorphism is in SPP ⋮ Isomorphic implication ⋮ Computing graph automorphism from partial solutions ⋮ The complexity of homomorphisms and renamings for minimal unsatisfiable formulas ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Restricted space algorithms for isomorphism on bounded treewidth graphs ⋮ On families of categorial grammars of bounded value, their learnability and related complexity questions ⋮ On Toda’s Theorem in Structural Communication Complexity ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Complexity and algorithms for computing Voronoi cells of lattices ⋮ Isomorphism and canonization of tournaments and hypertournaments ⋮ Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs ⋮ Dot operators ⋮ Compatible topologies on graphs: an application to graph isomorphism problem complexity ⋮ Reductions to Graph Isomorphism ⋮ On the pseudo-achromatic number problem ⋮ Solution-Graphs of Boolean Formulas and Isomorphism ⋮ Computational complexity of computing a partial solution for the graph automorphism problems ⋮ Permutation Groups and the Graph Isomorphism Problem ⋮ On the Complexity of Matroid Isomorphism Problems ⋮ Laminar structure of ptolemaic graphs with applications ⋮ Parameterized complexity of small weight automorphisms and isomorphisms ⋮ Do there exist complete sets for promise classes? ⋮ \texttt{SymChaff}: Exploiting symmetry in a structure-aware satisfiability solver ⋮ Unnamed Item ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ The complexity of equivalence and isomorphism of systems of equations over finite groups ⋮ The Decidability of the Structural Congruence for Beta-binders ⋮ Solution-Graphs of Boolean Formulas and Isomorphism1 ⋮ Restrictive Acceptance Suffices for Equivalence Problems