Isomorphism testing via polynomial-time graph extensions

DOI10.1007/S10852-010-9145-XMaRDI QIDQ662128zbMATH OpenOpenAlexFDO

Authors Daniel Cosmin Porumbel

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

zbMATH Keywords

graph isomorphismpolynomial extensionGI-ext

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A spectral assignment approach for the graph isomorphism problem
• Isomorphism testing algorithm for graphs: Incidence degree sequence method and applications
• A graph isomorphism algorithm for object recognition
• Attacks on hard instances of graph isomorphism
• McKay's canonical graph labeling algorithm

Cites work

• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
• A distance measure between attributed relational graphs for pattern recognition
• A large database of graphs and its use for benchmarking graph isomorphism algorithms
• A molecular structure matching problem
• A note on the derivation of maximal common subgraphs of two directed or undirected graphs
• An Algorithm for Subgraph Isomorphism
• An Efficient Algorithm for Graph Isomorphism
• Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs
• Evolutionary Computation in Combinatorial Optimization
• Graph isomorphism problem
• Inexact graph matching by means of estimation of distribution algorithms
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On the editing distance between unordered labeled trees
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Optimization by simulated annealing
• Random Graph Isomorphism

Cited in

(12)

• Simulated annealing algorithm for detecting graph isomorphism
• An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants
• Isomorphism testing algorithm for graphs: Incidence degree sequence method and applications
• Parallel Algorithm for Solving the Graph Isomorphism Problem
• Extending partial isomorphisms of graphs
• scientific article; zbMATH DE number 2102042 (Why is no real title available?)
• A general comparative study of some aspects of graph isomorphism
• Linear matching-time algorithm for the directed graph isomorphism problem
• scientific article; zbMATH DE number 4060741 (Why is no real title available?)
• Filtering graphs to check isomorphism and extracting mapping by using the conductance electrical model
• scientific article; zbMATH DE number 3968624 (Why is no real title available?)
• Efficient Method to Perform Isomorphism Testing of Labeled Graphs

Describes a project that uses

Uses Software

• bliss

This page was built for publication: Isomorphism testing via polynomial-time graph extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q662128)