Isomorphism of graphs of bounded valence can be tested in polynomial time

DOI10.1016/0022-0000(82)90009-5zbMath0493.68064OpenAlexW1974672137WikidataQ56503919 ScholiaQ56503919MaRDI QIDQ1168744

Publication date: 1982

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(82)90009-5

zbMATH Keywords

primitive permutation groups group actions orbit graph isomorphism problem colour automorphism problem for groups with composition factors of bounded order

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Coloring of graphs and hypergraphs (05C15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (only showing first 100 items - show all)

Isomorphism Testing for Graphs Excluding Small Minors ⋮ Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ On the Combinatorial Power of the Weisfeiler-Lehman Algorithm ⋮ On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness ⋮ An approach to parallel algorithm design ⋮ Classifying the finite simple groups ⋮ Canonical representations of partial 2-and 3-trees ⋮ Unnamed Item ⋮ Some recognition problems related to graph isomorphism ⋮ On the length of subgroup chains in the symmetric group ⋮ On the complexity of graph reconstruction ⋮ An improved isomorphism test for bounded-tree-width graphs ⋮ Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract) ⋮ Order Reconfiguration under Width Constraints ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ Computer algebra in probability and statistics ⋮ A Faster Isomorphism Test for Graphs of Small Degree ⋮ Comparison of Atom Maps ⋮ Normalisers of primitive permutation groups in quasipolynomial time ⋮ On convex relaxation of graph isomorphism ⋮ Two-closure of rank \(3\) groups in polynomial time ⋮ Directed path graph isomorphism ⋮ Isomorphism Testing Parameterized by Genus and Beyond ⋮ Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Space Complexity of k-Tree Isomorphism ⋮ The complexity of computing the automorphism group of automata and related problems ⋮ Spectrally Robust Graph Isomorphism ⋮ Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas ⋮ Causal nets or what is a deterministic computation? ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ A nonadaptive NC checker for permutation group intersection ⋮ Benchmark Graphs for Practical Graph Isomorphism ⋮ Ego‐centered and local roles: A graph theoretic approach ⋮ Unnamed Item ⋮ State Isomorphism in Model Programs with Abstract Data Structures ⋮ Graph isomorphism restricted by lists ⋮ Approximately Counting Embeddings into Random Graphs ⋮ Quantum algorithms for algebraic problems ⋮ The Structure of Level-k Phylogenetic Networks ⋮ Efficient Suboptimal Graph Isomorphism ⋮ On the Complexity of Matroid Isomorphism Problems ⋮ Graph isomorphism is low for PP ⋮ Treewidth of display graphs: bounds, brambles and applications ⋮ Recognizing generalized Sierpiński graphs ⋮ Unnamed Item ⋮ Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs ⋮ Computational Complexity of Computing Symmetries in Finite-Domain Planning ⋮ Combinatorial invariant for Morse–Smale diffeomorphisms on surfaces with orientable heteroclinic ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree ⋮ Solution-Graphs of Boolean Formulas and Isomorphism1 ⋮ Random Models and Analyses for Chemical Graphs ⋮ Restrictive Acceptance Suffices for Equivalence Problems ⋮ Canonisation and Definability for Graphs of Bounded Rank Width ⋮ Polynomial isomorphism algorithm for graphs which do not pinch to \(K_{3,g}\) ⋮ Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time ⋮ Graph algebras and the graph isomorphism problem ⋮ On the construction of parallel computers from various basis of Boolean functions ⋮ The QAP-polytope and the graph isomorphism problem ⋮ New invariants for the graph isomorphism problem ⋮ Generalized quantifiers and pebble games on finite structures ⋮ Graph isomorphism parameterized by elimination distance to bounded degree ⋮ Isomorphism of chordal (6, 3) graphs ⋮ Graph embedding in SYNCHEM2, an expert system for organic synthesis discovery ⋮ Matching graphs with unique node labels ⋮ Computing the structure of finite algebras ⋮ On the geometric graph isomorphism problem ⋮ Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's conjecture confirmed ⋮ Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes ⋮ Optimal-depth sorting networks ⋮ Choiceless Polynomial Time on Structures with Small Abelian Colour Classes ⋮ Graph isomorphism for graph classes characterized by two forbidden induced subgraphs ⋮ Parallel algorithms for solvable permutation groups ⋮ An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants ⋮ Strong tree-cographs are Birkhoff graphs ⋮ Pruning the search tree in the constructive enumeration of molecular graphs ⋮ Bases for primitive permutation groups and a conjecture of Babai ⋮ Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ General linear group action on tensors: a candidate for post-quantum cryptography ⋮ A long trip in the charming world of graphs for pattern recognition ⋮ On the complexity of submap isomorphism and maximum common submap problems ⋮ Efficient subgraph matching using topological node feature constraints ⋮ Approximation of graph edit distance based on Hausdorff matching ⋮ On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism ⋮ Filtering graphs to check isomorphism and extracting mapping by using the conductance electrical model ⋮ Computational complexity of reconstruction and isomorphism testing for designs and line graphs ⋮ A time-based solution for the graph isomorphism problem ⋮ On the isomorphism of graphs having some eigenvalues of moderate multiplicity ⋮ Cleaning interval graphs ⋮ Symmetric blocking ⋮ Towards an isomorphism dichotomy for hereditary graph classes ⋮ Completeness results for graph isomorphism. ⋮ Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs ⋮ Space efficient representations of finite groups ⋮ An optimal construction of Hanf sentences ⋮ A computational approach to construct a multivariate complete graph invariant ⋮ Isomorphism testing of k-trees is in NC, for fixed k ⋮ On the complexity of matroid isomorphism problem ⋮ Practical graph isomorphism. II.

Cites Work

This page was built for publication: Isomorphism of graphs of bounded valence can be tested in polynomial time