Group-theoretic algorithms and graph isomorphism

zbMath0487.68055MaRDI QIDQ1165581

Christoph M. Hoffmann

Publication date: 1982

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

trivalent graphsgraph automorphismsgenerating permutationsgraph isomorphism problemcone graphs

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) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Algorithms in computer science (68W99)

Related Items (52)

Vulnerability analysis of multiprocessor system based on burnt pancake networks ⋮ Generic case complexity of the graph isomorphism problem ⋮ A general backtrack algorithm for the isomorphism problem of combinatorial objects ⋮ Graph embedding in SYNCHEM2, an expert system for organic synthesis discovery ⋮ Neighbor-connectivity of pancake networks and burnt pancake networks ⋮ The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ Asymptotic results for primitive permutation groups ⋮ On the computational complexity of the Abelian permutation group structure, membership and intersection problems ⋮ Intersecting subgroups of finite soluble groups ⋮ Parallel algorithms for solvable permutation groups ⋮ A graph isomorphism algorithm using pseudoinverses ⋮ Graph isomorphism is in the low hierarchy ⋮ Unnamed Item ⋮ Strong tree-cographs are Birkhoff graphs ⋮ Permutative rewriting and unification ⋮ Analysis on component connectivity of bubble-sort star graphs and burnt pancake graphs ⋮ Solvable black-box group problems are low for PP ⋮ Computational complexity of reconstruction and isomorphism testing for designs and line graphs ⋮ Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays ⋮ A Logspace Algorithm for Partial 2-Tree Canonization ⋮ Target set selection on generalized pancake graphs ⋮ Fast computation of the centralizer of a permutation group in the symmetric group ⋮ A novel approach to perturbative calculations for a large class of interacting boson theories ⋮ Parallel rewriting of attributed graphs ⋮ A proof of Holt's algorithm ⋮ Efficient algorithmic learning of the structure of permutation groups by examples ⋮ Learnability of quantified formulas. ⋮ Neighborhood hypergraphs of bipartite graphs ⋮ Graph isomorphism and identification matrices: Sequential algorithms ⋮ Exploring the tractability border in epistemic tasks ⋮ Polynomial-time algorithms for testing strong isomorphism and computing the automorphism group of \(R\)-strongly connected automata ⋮ Permutation group algorithms based on partitions. I: Theory and algorithms ⋮ Symmetric ILP: Coloring and small integers ⋮ An Inductive Schema for Computing Conjugacy Classes in Permutation Groups ⋮ Graph isomorphism is low for PP ⋮ Linear and sublinear time algorithms for the basis of abelian groups ⋮ A nonadaptive NC checker for permutation group intersection ⋮ Graph Isomorphism is in SPP ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Reductions to graph isomorphism ⋮ Hashing and canonicalizing Notation 3 graphs ⋮ Reductions to Graph Isomorphism ⋮ A new approach to operating with undirected trees ⋮ Quantum algorithms for algebraic problems ⋮ The complexity of homomorphism factorization ⋮ Efficient comparison of program slices ⋮ Graph isomorphism is low for PP ⋮ The counting complexity of group-definable languages ⋮ Fault tolerance and diagnosability of burnt pancake networks under the comparison model ⋮ Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra ⋮ Restrictive Acceptance Suffices for Equivalence Problems ⋮ Computing in general Abelian groups is hard

This page was built for publication: Group-theoretic algorithms and graph isomorphism