A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation

DOI10.1007/s10878-020-00598-wzbMath1467.05174OpenAlexW3034005920MaRDI QIDQ2023115

Pawan Aurora, Shashank K. Mehta

Publication date: 3 May 2021

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-020-00598-w

zbMATH Keywords

quadratic assignment problemgraph isomorphismLovász theta function

Mathematics Subject Classification ID

Linear programming (90C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Copositive and semidefinite relaxations of the quadratic assignment problem
• An optimal lower bound on the number of variables for graph identification
• Geometric algorithms and combinatorial optimization
• The QAP-polytope and the graph isomorphism problem
• Using a factored dual in augmented Lagrangian methods for semidefinite programming
• Sherali-Adams relaxations of graph isomorphism polytopes
• Genus characterizes the complexity of certain graph problems: Some tight results
• Global Optimization with Polynomials and the Problem of Moments
• Approximation of the Stability Number of a Graph via Copositive Programming
• On the Shannon capacity of a graph
• Reducibility among Combinatorial Problems
• Graph isomorphism in quasipolynomial time [extended abstract]
• Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs

This page was built for publication: A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation