Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes

DOI10.1080/09720529.2020.1732084zbMath1490.52011arXiv1705.10081OpenAlexW3032096057MaRDI QIDQ5865703

Aleksandr N. Maksimenko

Publication date: 9 June 2022

Published in: Journal of Discrete Mathematical Sciences and Cryptography (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.10081

zbMATH Keywords

graph isomorphismYoung polytopesBirkhoff polytopespermutation polytopesaffine reduction3-neighborlyBoolean quadratic polytopes

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Cites Work

• Unnamed Item
• Unnamed Item
• Geometry, complexity, and combinatorics of permutation polytopes
• A study of the quadratic semi-assignment polytope
• Two graph isomorphism polytopes
• An analog of the Cook theorem for polytopes
• \(k\)-neighborly faces of the Boolean quadric polytopes
• The common face of some 0/1-polytopes with NP-complete nonadjacency relation
• A short proof that the extension complexity of the correlation polytope grows exponentially
• Boolean quadric polytopes are faces of linear ordering polytopes
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Traveling salesman polytopes and cut polytopes. Affine reducibility
• The cut cone. III: On the role of triangle facets
• Geometry of cuts and metrics

This page was built for publication: Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes