Graph isomorphism problem
From MaRDI portal
Publication:1057883
DOI10.1007/BF02104746zbMath0564.05049MaRDI QIDQ1057883
N. M. Kornienko, V. N. Zemlyachenko, Regina I. Tyshkevich
Publication date: 1985
Published in: Journal of Soviet Mathematics (Search for Journal in Brave)
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)
Related Items
Binets: fundamental building blocks for phylogenetic networks ⋮ On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness ⋮ Isomorphism testing for \(T\)-graphs in FPT ⋮ An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants ⋮ Almost equitable partitions and controllability of leader-follower multi-agent systems ⋮ Computational complexity of reconstruction and isomorphism testing for designs and line graphs ⋮ On the isomorphism of graphs having some eigenvalues of moderate multiplicity ⋮ Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs ⋮ A computational approach to construct a multivariate complete graph invariant ⋮ Unnamed Item ⋮ Maximum common induced subgraph parameterized by vertex cover ⋮ Isomorphism testing via polynomial-time graph extensions ⋮ Lorentzian spectral geometry with causal sets ⋮ Unnamed Item ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Polynomial equivalence of the problems ``predicate formulas isomorphism and graph isomorphism ⋮ Permutation Groups and the Graph Isomorphism Problem ⋮ The Structure of Level-k Phylogenetic Networks ⋮ Computational Complexity of Computing Symmetries in Finite-Domain Planning ⋮ Isomorphic unordered labeled trees up to substitution ciphering
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of symmetrizing matrices
- The complexity of computing the permanent
- Groups with a small number of automorphisms
- On deciding switching equivalence of graphs
- A correction to Colbourn's paper on the complexity of matrix symmetrizability
- Le problème d'étoiles pour graphes est NP-complèt
- Two reductions of graph isomorphism to problems on polynomials
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- On counting problems and the polynomial-time hierarchy
- On the ratio of optimal integral and fractional covers
- Coherent configurations. I: Ordinary representation theory
- On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
- A note on the graph isomorphism counting problem
- Hadamard equivalence via graph isomorphism
- Graph isomorphism, general remarks
- Graph 2-isomorphism is NP-complete
- Complexity of wild matrix problems and of isomorphism of algebras and graphs
- Graph isomorphism: A heuristic edge-partitioning-oriented algorithm
- On full embeddings of categories of algebras
- Describing an algorithm by Hopcroft
- Isomorfismo fra grafi: un algoritmo efficiente per trovare tutti gli isomorfismi
- Further annotated bibliography on the isomorphism disease
- Isomorphism Testing and Symmetry of Graphs
- On the Complexity of Canonical Labeling of Strongly Regular Graphs
- A Theoretical Analysis of Various Heuristics for the Graph Isomorphism Problem
- The Complexity of Combinatorial Isomorphism Problems
- Random Graph Isomorphism
- Some NP-Complete Problems Similar to Graph Isomorphism
- On testing isomorphism of permutation graphs
- Efficient Planarity Testing
- An Algorithm for Finding the Blocks of a Permutation Group
- On a certain distance between isomorphism classes of graphs
- A new algorithm for digraph isomorphism
- The graph isomorphism disease
- Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- A Set of Topological Invariants for Graphs
- On the Classification of Graphs
- 2-Isomorphic Graphs
- Dividing a Graph into Triconnected Components
- On the nlog n isomorphism technique (A Preliminary Report)
- Note on Isomorphisms of Graphs
- Generalized Matrix Functions and the Graph Isomorphism Problem
- An Efficient Algorithm for Graph Isomorphism
- Graphs and k-Societies
- Asymmetric graphs
- GIT—a heuristic program for testing pairs of directed line graphs for isomorphism
- Lattices With a Given Abstract Group of Automorphisms
