|
Fundamentalnaya i Prikladnaya Matematika, 2013, Volume 18, Issue 2, Pages 105–118
(Mi fpm1502)
|
|
|
|
This article is cited in 8 scientific papers (total in 8 papers)
The common face of some $0/1$-polytopes with NP-complete nonadjacency relation
A. N. Maksimenko P. G. Demidov Yaroslavl State University, Yaroslavl, Russia
Abstract:
In this paper, we consider so-called double covering polytopes. In 1995, Matsui showed that the problem of checking nonadjacency on these polytopes is NP-complete. We show that double covering polytopes are faces of the following polytopes: knapsack polytopes, set covering polytopes, cubic subgraph polytopes, $3$-SAT polytopes, partial order polytopes, traveling salesman polytopes, and some others.
Citation:
A. N. Maksimenko, “The common face of some $0/1$-polytopes with NP-complete nonadjacency relation”, Fundam. Prikl. Mat., 18:2 (2013), 105–118; J. Math. Sci., 203:6 (2014), 823–832
Linking options:
https://www.mathnet.ru/eng/fpm1502 https://www.mathnet.ru/eng/fpm/v18/i2/p105
|
Statistics & downloads: |
Abstract page: | 287 | Full-text PDF : | 123 | References: | 52 | First page: | 1 |
|