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

GI-extgraph isomorphismpolynomial extension

Mathematics Subject Classification ID

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) Graph theory (including graph drawing) in computer science (68R10)

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

• A distance measure between attributed relational graphs for pattern recognition
• A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
• 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
• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Inexact graph matching by means of estimation of distribution algorithms
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• On the editing distance between unordered labeled trees
• Optimization by simulated annealing
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Random Graph Isomorphism

Cited in

(13)

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

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)