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
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
