RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2015, том 22, выпуск 1, страницы 19–31 (Mi da804)

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

Об одной экстремальной обратной задаче теории графов

А. Б. Дайняк, А. Д. Курносов

Московский физико-технический институт, Институтский пер., 9, 141700 Долгопрудный, Россия

Аннотация: Рассматривается задача построения графа, имеющего заданное количество независимых множеств. Получены оценки на количество вершин в двудольных графах с предписанным числом независимых множеств и числом максимальных по включению независимых множеств. Ил. 1, библиогр. 6.

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

УДК: 519.176

Статья поступила: 11.03.2014
Переработанный вариант: 12.09.2014

DOI: 10.17377/daio.2015.22.445


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2015, 9:2, 157–164

Реферативные базы данных:


© МИАН, 2024