A convex relaxation bound for subgraph isomorphism

DOI10.1155/2012/908356zbMath1236.05133OpenAlexW1966242563WikidataQ58703379 ScholiaQ58703379MaRDI QIDQ666533

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Uses Software

• CSDP
• PENNON
• Benchmarks for Optimization Software

Cites Work

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

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