|
Фундаментальная и прикладная математика, 2013, том 18, выпуск 2, страницы 105–118
(Mi fpm1502)
|
|
|
|
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)
Общая грань некоторых $0/1$-многогранников с NP-полным критерием несмежности вершин
А. Н. Максименко Ярославский государственный университет им. П. Г. Демидова
Аннотация:
В работе рассматриваются многогранники двойных покрытий. В 1995 г. Мацуи установил, что задача проверки несмежности вершин для этих многогранников NP-полна. Мы покажем, что многогранники двойных покрытий являются гранями многогранников, ассоциированных со следующими задачами: задача о рюкзаке, задача о покрытии множества, задача о кубическом подграфе, задача о $3$-выполнимости, задача о частичном упорядочении, задача коммивояжёра и некоторые другие.
Ключевые слова:
NP-полные задачи, многогранники, смежные вершины, грани.
Образец цитирования:
А. Н. Максименко, “Общая грань некоторых $0/1$-многогранников с NP-полным критерием несмежности вершин”, Фундамент. и прикл. матем., 18:2 (2013), 105–118; J. Math. Sci., 203:6 (2014), 823–832
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/fpm1502 https://www.mathnet.ru/rus/fpm/v18/i2/p105
|
Статистика просмотров: |
Страница аннотации: | 287 | PDF полного текста: | 123 | Список литературы: | 52 | Первая страница: | 1 |
|