On affine reducibility of combinatorial polytopes

DOI10.1134/S1064562412020123zbMath1262.90148MaRDI QIDQ1761001

Aleksandr N. Maksimenko

Publication date: 15 November 2012

Published in: Doklady Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-completenonadjacency

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (5)

On a family of \(0/1\)-polytopes with an NP-complete criterion for vertex nonadjacency relation ⋮ \(k\)-neighborly faces of the Boolean quadric polytopes ⋮ The common face of some 0/1-polytopes with NP-complete nonadjacency relation ⋮ Combinatorial structure and adjacency of vertices of polytope of \(b\)-factors ⋮ The simplest families of polytopes associated with NP-hard problems

Cites Work

• Adjacency on the constrained assignment problem
• A combinatorial study of partial order polytopes
• The adjacency relation on the traveling salesman polytope is NP-Complete
• Unnamed Item

This page was built for publication: On affine reducibility of combinatorial polytopes