Approximate graph isomorphism

DOI10.1007/978-3-642-32589-2_12MaRDI QIDQ2912712zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Sebastian Kuhnert, Yadu Vasudev, Johannes Köbler

Publication date 25 September 2012

Published in Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32589-2_12

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• On the approximability of the maximum common subgraph problem
• Isomorphism of (mis)Labeled Graphs
• Graph similarity and approximate isomorphism
• Algorithms for approximate graph matching
• Complexity of approximating bounded variants of optimization problems

Cited in

(15)

• Approximate graph products
• Detecting almost symmetries of graphs
• De-anonymization of heterogeneous random graphs in quasilinear time
• Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
• scientific article; zbMATH DE number 5525608 (Why is no real title available?)
• An algorithm for optimal isomorphism between two random graphs
• An algorithm using length-r paths to approximate subgraph isomorphism
• scientific article; zbMATH DE number 1839469 (Why is no real title available?)
• Lov\'asz Meets Weisfeiler and Leman
• Graph similarity and approximate isomorphism
• Isomorphic Distances Among Elections
• The Complexity of Homomorphism Indistinguishability
• Benchmark Graphs for Practical Graph Isomorphism
• Succinct Encodings of Graph Isomorphism
• How similar are two elections?

This page was built for publication: Approximate graph isomorphism

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