ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2013, ТОМ 18, ВЫПУСК 2, СТР. 105-118

Общая грань некоторых $0/1$-многогранников с NP-полным критерием несмежности вершин

А. Н. Максименко

Аннотация

Посмотреть как HTML    Посмотреть как рисунок

В работе рассматриваются многогранники двойных покрытий. В 1995 г. Мацуи установил, что задача проверки несмежности вершин для этих многогранников NP-полна. Мы покажем, что многогранники двойных покрытий являются гранями многогранников, ассоциированных со следующими задачами: задача о рюкзаке, задача о покрытии множества, задача о кубическом подграфе, задача о $3$-выполнимости, задача о частичном упорядочении, задача коммивояжёра и некоторые другие.

Полнотекстовая версия статьи в формате PDF (185 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k13/k132/k13208h.htm
Изменения вносились 7 января 2014 г.