The QAP-polytope and the graph isomorphism problem

DOI10.1007/s10878-018-0266-xzbMath1412.90087OpenAlexW2788334612MaRDI QIDQ1631655

Pawan Aurora, Shashank K. Mehta

Publication date: 6 December 2018

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

Full work available at URL: https://doi.org/10.1007/s10878-018-0266-x

zbMATH Keywords

quadratic assignment problempolyhedral combinatoricsgraph isomorphism problem

Mathematics Subject Classification ID

Integer programming (90C10) Discrete location and assignment (90B80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (2)

Computing Autotopism Groups of Partial Latin Rectangles ⋮ A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation

Uses Software

• nauty
• Traces

Cites Work

• Copositive and semidefinite relaxations of the quadratic assignment problem
• Does co-NP have short interactive proofs ?
• Graph isomorphism is in the low hierarchy
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• A note on compact graphs
• An optimal lower bound on the number of variables for graph identification
• A note on the graph isomorphism counting problem
• Sherali-Adams relaxations of graph isomorphism polytopes
• Practical graph isomorphism. II.
• Global Optimization with Polynomials and the Problem of Moments
• Sherali-Adams relaxations and indistinguishability in counting logics
• On the automorphism groups of strongly regular graphs I
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Interval Graphs: Canonical Representation in Logspace
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• Algorithmic Techniques for the Generation and Analysis of Strongly Regular Graphs and other Combinatorial Configurations
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Pebble Games and Linear Equations
• Efficient Parallel Algorithms for Chordal Graphs
• Reducibility among Combinatorial Problems
• Isomorphism of Planar Graphs (Working Paper)
• Graph isomorphism in quasipolynomial time [extended abstract]
• Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• Simple Geometrical Intersection Graphs
• Box-inequalities for quadratic assignment polytopes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The QAP-polytope and the graph isomorphism problem