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