A convex relaxation bound for subgraph isomorphism

DOI10.1155/2012/908356MaRDI QIDQ666533zbMATH OpenOpenAlexWikidataFDO

Authors Christian Schellewald

Publication date 8 March 2012

Published in International Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1155/2012/908356

zbMATH Keywords

combinatorial optimization problem, Error-correcting graph matching

Mathematics Subject Classification ID

Combinatorial optimization (90C27) 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 Bound for Non-subgraph Isomorphism
• On convex relaxation of graph isomorphism
• Two graph isomorphism polytopes
• Filtering for Subgraph Isomorphism
• Subgraph Matching with Semidefinite Programming

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 4083968 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1222894 (Why is no real title available?)
• scientific article; zbMATH DE number 1131479 (Why is no real title available?)
• scientific article; zbMATH DE number 2040634 (Why is no real title available?)
• scientific article; zbMATH DE number 2068039 (Why is no real title available?)
• A distance measure between attributed relational graphs for pattern recognition
• An Algorithm for Subgraph Isomorphism
• An Interior-Point Method for Semidefinite Programming
• An independent benchmarking of SDP and SOCP solvers
• Benchmarks for Optimization Software
• CSDP 2.3 user's guide
• CSDP, A C library for semidefinite programming
• Exact bounds on the order of the maximum clique of a graph.
• Graph-Based Representations in Pattern Recognition
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Quadratic programming with one negative eigenvalue is NP-hard
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Subgraph isomorphism, matching relational structures and maximal cliques

Cited in

(6)

• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• A Bound for Non-subgraph Isomorphism
• On convex relaxation of graph isomorphism
• New bounds for subset selection from conic relaxations
• A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation
• Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable

Describes a project that uses

Uses Software

• CSDP
• PENNON
• Benchmarks for Optimization Software

This page was built for publication: A convex relaxation bound for subgraph isomorphism

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