Задача о максимальном K-подграфе

Владимир Николаевич Бурков, Александр Рудольфович Кашенков, Виктор Дмитриевич Кондратьев

Аннотация


Вводится понятие K-подграфа как подграфа, каждая компонента которого содержит не более K вершин. Ставится задача определения максимального K-графа, то есть K-графа с максимальным числом вершин. Дается решение задачи для дерева. Для случая K = 2 предложены два эвристических алгоритма. Приведен пример прикладной задачи формирования портфеля с учетом взаимозависимости проектов, алгоритм решения которой включает этап определения максимального K-подграфа.


Ключевые слова


K-подграф; дерево; эвристические алгоритмы; взаимозависимые проекты

Полный текст:

PDF

Литература


Буркова, И.В. Метод сетевого программирования в задачах нелинейной оптимизации / И.В. Буркова // Автоматика и телемеханика. – 2009. – № 10. – С. 15–21.

Буркова, И.В. Метод сетевого программирования в задаче целочисленного линейного программирования / И.В. Буркова, А.Р. Кашенков // Теория активных систем – 2011. Труды международной научно-практической конференции. – М.: Институт проблем управления РАН, 2011. – С. 25–26.




DOI: http://dx.doi.org/10.14529/ctcr180102

Ссылки

  • На текущий момент ссылки отсутствуют.