Я. А. Ловеров, Ю. Л. Орлович, “NP-полнота задачи о независимом доминирующем множестве в классе кубических планарных двудольных графов”, Дискретн. анализ и исслед. опер., 2020, том 27, выпуск 2,страницы 65

Эта публикация цитируется в 3 статьях

NP-полнота задачи о независимом доминирующем множестве в классе кубических планарных двудольных графов

Я. А. Ловеров, Ю. Л. Орлович

Белорусский гос. университет, пр. Независимости, 4, 220030 Минск, Беларусь

Аннотация: Известно, что как в классе кубических планарных графов, так и в классе кубических двудольных графов задача о независимом доминирующем множестве NP-полна. Вопрос о вычислительной сложности данной задачи в пересечении вышеупомянутых классов является открытым. В настоящей работе доказывается, что в классе кубических планарных двудольных графов задача о независимом доминирующем множестве также NP-полна. Табл. 1, ил. 7, библиогр. 19.

Ключевые слова: независимое доминирующее множество, кубический граф, планарный граф, двудольный граф, NP-полнота.

УДК: 519.17

Статья поступила: 11.04.2019
Переработанный вариант: 20.12.2019
Принята к публикации: 13.01.2020

DOI: 10.33048/daio.2020.27.657