Задача о максимальном K-подграфе
DOI:
https://doi.org/10.14529/ctcr180102Ключевые слова:
K-подграф, дерево, эвристические алгоритмы, взаимозависимые проектыАннотация
Вводится понятие K-подграфа как подграфа, каждая компонента которого содержит не более K вершин. Ставится задача определения максимального K-графа, то есть K-графа с максимальным числом вершин. Дается решение задачи для дерева. Для случая K = 2 предложены два эвристических алгоритма. Приведен пример прикладной задачи формирования портфеля с учетом взаимозависимости проектов, алгоритм решения которой включает этап определения максимального K-подграфа.
Библиографические ссылки
Буркова, И.В. Метод сетевого программирования в задачах нелинейной оптимизации / И.В. Буркова // Автоматика и телемеханика. – 2009. – № 10. – С. 15–21.
Буркова, И.В. Метод сетевого программирования в задаче целочисленного линейного программирования / И.В. Буркова, А.Р. Кашенков // Теория активных систем – 2011. Труды международной научно-практической конференции. – М.: Институт проблем управления РАН, 2011. – С. 25–26.
