Isomorphism testing via polynomial-time graph extensions
From MaRDI portal
Publication:662128
DOI10.1007/s10852-010-9145-xzbMath1238.05175MaRDI QIDQ662128
Publication date: 21 February 2012
Published in: JMMA. Journal of Mathematical Modelling and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10852-010-9145-x
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Optimization by Simulated Annealing
- Graph isomorphism problem
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- On the editing distance between unordered labeled trees
- A molecular structure matching problem
- Inexact graph matching by means of estimation of distribution algorithms
- A note on the derivation of maximal common subgraphs of two directed or undirected graphs
- Random Graph Isomorphism
- Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
- An Algorithm for Subgraph Isomorphism
- A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
- Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
- A large database of graphs and its use for benchmarking graph isomorphism algorithms
- A distance measure between attributed relational graphs for pattern recognition
- Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs
- An Efficient Algorithm for Graph Isomorphism
- Evolutionary Computation in Combinatorial Optimization