A note on the graph isomorphism counting problem
From MaRDI portal
Publication:1253098
DOI10.1016/0020-0190(79)90004-8zbMath0395.68057OpenAlexW1989114462MaRDI QIDQ1253098
Publication date: 1979
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(79)90004-8
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Related Items (58)
Graph algebras and the graph isomorphism problem ⋮ On computation complexity problems concerning relation algebras ⋮ Detecting almost symmetries of graphs ⋮ The complexity of Boolean matrix root computation ⋮ The QAP-polytope and the graph isomorphism problem ⋮ New invariants for the graph isomorphism problem ⋮ A short certificate of the number of universal optimal strategies for stopping simple stochastic games ⋮ Representing Groups on Graphs ⋮ Information theoretic measures of UHG graphs with low computational complexity ⋮ Graph isomorphism is in the low hierarchy ⋮ 3-connected reduction for regular graph covers ⋮ An improved isomorphism test for bounded-tree-width graphs ⋮ On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism ⋮ Generalized X-join of graphs and their automorphisms ⋮ On the Complexity of the Hidden Subgroup Problem ⋮ On tail dependence matrices. The realization problem for parametric families ⋮ On the isomorphism of graphs having some eigenvalues of moderate multiplicity ⋮ On multidimensional Schur rings of finite groups ⋮ Comparison of Atom Maps ⋮ Two-closure of rank \(3\) groups in polynomial time ⋮ On the complexity of computational problems associated with simple stochastic games ⋮ Isomorphism Testing Parameterized by Genus and Beyond ⋮ Symmetry Breaking Constraints for the Minimum Deficiency Problem ⋮ Generalizations of \(k\)-dimensional Weisfeiler-Leman stabilization ⋮ Unnamed Item ⋮ On complete systems of invariants for small graphs ⋮ On counting problems and the polynomial-time hierarchy ⋮ Pseudo-deterministic Proofs ⋮ Investigation graph isomorphism problem via entanglement entropy in strongly regular graphs ⋮ Computing functions with parallel queries to NP ⋮ Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas ⋮ Configuring Random Graph Models with Fixed Degree Sequences ⋮ Uniquely pressable graphs: characterization, enumeration, and recognition ⋮ An optimal lower bound on the number of variables for graph identification ⋮ ON THE COMPLEXITY OF THE HIDDEN SUBGROUP PROBLEM ⋮ On the asymmetric complexity of the group-intersection problem ⋮ Graph isomorphism is low for PP ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs ⋮ Graph Isomorphism is in SPP ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Parameterized counting of partially injective homomorphisms ⋮ Graph isomorphism restricted by lists ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ Computational complexity of computing a partial solution for the graph automorphism problems ⋮ Permutation Groups and the Graph Isomorphism Problem ⋮ Graph isomorphism is low for PP ⋮ Parameterized complexity of small weight automorphisms and isomorphisms ⋮ Structural sparsity of complex networks: bounded expansion in random models and real-world graphs ⋮ The counting complexity of group-definable languages ⋮ Subcomplete generalizations of graph isomorphism ⋮ Drawing series parallel digraphs symmetrically ⋮ On a new high dimensional Weisfeiler-Lehman algorithm ⋮ Computational Complexity of Computing Symmetries in Finite-Domain Planning ⋮ The complexity of equivalence and isomorphism of systems of equations over finite groups ⋮ Graph isomorphism problem ⋮ Graph isomorphism problem and \(2\)-closed permutation groups ⋮ Testing homotopy equivalence is isomorphism complete
Cites Work
This page was built for publication: A note on the graph isomorphism counting problem
