The Problem of the Maximal K-Subgraph
DOI:
https://doi.org/10.14529/ctcr180102Keywords:
K-subgraph, tree, heuristic algorithms, interdependent projectsAbstract
We introduce the notion of a K-subgraph as a subgraph, each component of which contains at most K vertices. The problem is to determine the maximal K-graph, that is, the K-graph with the maximum number of vertices. The solution of the problem for a tree is given. For the case K = 2 two heuristic algorithms are proposed. An example of the applied task of portfolio formation is given taking into account the interdependence of projects, the algorithm for solving which includes the stage of determining the maximum K-subgraph.
References
Буркова, И.В. Метод сетевого программирования в задачах нелинейной оптимизации / И.В. Буркова // Автоматика и телемеханика. – 2009. – № 10. – С. 15–21.
Буркова, И.В. Метод сетевого программирования в задаче целочисленного линейного программирования / И.В. Буркова, А.Р. Кашенков // Теория активных систем – 2011. Труды международной научно-практической конференции. – М.: Институт проблем управления РАН, 2011. – С. 25–26.
