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

From MaRDI portal

Publication:1168744

Jump to:navigation, search

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

Eugene M. Luks

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

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., The graph isomorphism problem and approximate categories, The isomorphism problem for planar 3-connected graphs is in unambiguous logspace, A polynomial bound for the orders of primitive solvable groups, On the orders of primitive groups with restricted nonabelian composition factors, Efficient algorithmic learning of the structure of permutation groups by examples, Isomorphism of graphs of bounded valence can be tested in polynomial time, kLog: a language for logical and relational learning with kernels, Confronting intractability via parameters, The module isomorphism problem reconsidered., On the automorphism groups of strongly regular graphs. II., Network alignment by discrete Ollivier-Ricci flow, An appraisal of computational complexity for operations researchers, A note on compact graphs, Graph isomorphism and identification matrices: Sequential algorithms, Isomorphism testing via polynomial-time graph extensions, Beating the generator-enumeration bound for \(p\)-group isomorphism, VF2++ -- an improved subgraph isomorphism algorithm, Polynomial-time algorithm for isomorphism of graphs with clique-width at most three, Grammatical inference of directed acyclic graph languages with polynomial time complexity, Learning an efficient constructive sampler for graphs, Canonical representations of partial 2- and 3-trees, On the diameter of permutation groups, On the complexity of finding iso- and other morphisms for partial \(k\)- trees, Isomorphism identification of graphs: especially for the graphs of kinematic chains, On the power of combinatorial and spectral invariants, An optimal lower bound on the number of variables for graph identification, On the asymmetric complexity of the group-intersection problem, Colored hypergraph isomorphism is fixed parameter tractable, Graph isomorphism is low for PP, Infinite labeled trees: from rational to Sturmian trees, Restricted space algorithms for isomorphism on bounded treewidth graphs, Graph theory (algorithmic, algebraic, and metric problems), Computing the composition factors of a permutation group in polynomial time, The smallest non-autograph, On algorithms that effectively distinguish gradient-like dynamics on surfaces, On short expressions for cosets of permutation subgroups, Determination of isomorphism and its applications for arbitrary graphs based on circuit simulation, Topological variability of collectives and its import for social epistemology, Solution-Graphs of Boolean Formulas and Isomorphism, On the coding of ordered graphs, A parametric filtering algorithm for the graph isomorphism problem, Permutation Groups and the Graph Isomorphism Problem, Efficient comparison of program slices, A graph isomorphism algorithm for object recognition, Mine ’Em All: A Note on Mining All Graphs, Algorithms for matrix groups and the Tits alternative, Subcomplete generalizations of graph isomorphism, Graph isomorphism problem, Classical symmetries and the quantum approximate optimization algorithm, Graph isomorphism problem and \(2\)-closed permutation groups, Sylow's theorem in polynomial time, No easy puzzles: hardness results for jigsaw puzzles, Quadratic forms and the graph isomorphism problem, Graph recurrence, Permutation groups without exponentially many orbits on the power set

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1168744&oldid=13235015"