Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений
Д. В. Грибанов1, Д. С. Малышев2
| Аннотация | В статье рассматриваются естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования. Для любого фиксированного $C$ в статье доказывается полиномиальная разрешимость обеих задач о доминирующем множестве в классе графов, у которых все миноры матриц смежности вершин или ребер не превосходят $C$ по абсолютному значению. В статье также доказывается подобный результат для задачи о независимом множестве и класса графов, который задается ограничением абсолютных значений всех миноров матриц, полученных пополнением транспонированных матриц инцидентности векторами из одних единиц. |
|---|---|
| Ключевые слова | булево линейное программирование, задача о независимом множестве, задача о доминирующем множестве, матричный минор, полиномиальный алгоритм |
1Ассистент кафедры алгебры, геометрии и дискретной математики, Нижегородский государственный университет им. Н. И. Лобачевского, dimitry.gribanov@gmail.com
2Профессор кафедры прикладной математики и информатики, Национальный исследовательский университет «Высшая школа экономики», Н. Новгород; dsmalyshev@rambler.ru
Цитирование: Грибанов Д. В., Малышев Д. С. Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений // Журнал Средневолжского математического общества. 2016. Т. 18, № 3. С. 19–31.
