Maximum independent sets of graph vertices searching for software projects improvement

O.O. Slabospitska, P.I. Stetsyuk, O.M. Khomiak


The need is fixed to software project enhancing with seamless integration of technological-descriptive and normative project manage- ment approaches by means of classical Graph Discrete Optimization Problems tailoring for software project management tasks, poorly equipped with best practices within technological approach. Class of software project management tasks is proposed to demonstrate the benefits of such integration. Two Boolean linear programming problems are investigated for searching some maximum size indepen- dent set (Section 1) and an algorithm for searching all possible maximum size independent sets (Section 2). Section 3 presents Problem Statement for searching a given number of non-intersecting independent sets with maximum sum of vertices’ numbers within independent sets. Based on it, Vizing-Plesnevich algorithm is described for coloring the graph vertices with the minimum number of colors.

To solve Boolean problems, both specialized mathematical programming language AMPL and corresponding solver program named gu- robi are used. For basic algorithms developed, reference AMPL code versions are given as well as their running results.

Illustrative examples of software project enhancing with the algorithms elaborated are considered in Section 4, namely: 25 specialists being conflicted during their previous projects partitioning into coherent conflict-free sub-teams for software projects portfolio; schedule optimization for autonomous testing of reusable components within a critical software system; cores composing for independent teams in a critical software project.

Prombles in programming 2022; 3-4: 73-84



software project; resource allocation; Boolean linear programming problem; independent set of graph vertices; minimal graph coloring; Vizing-Plesnevich algorithm

Full Text:

PDF (Ukrainian)


A Guide to the Project Management Body of Knowledge (PMBOK Guide) – and the Standard for Project Management [7 ed.]. Newton Square, Pennsylvanya: Project management Institute, Inc, 2021. – 370 p.

Barkalov, S.A., Burkov V.N., Gelrud Ya.D. et al. (2019) Smart Project Management: A Manual. Chelyabinsk:YurGU Publishers. – 189 p.

Stetsyuk, P.I., Slabospitska O.O., Ushakova O.O. (2016) Maximal independent sets of graph vertices and their application in project management. Pytannya prykladnoyi matematyky i matematychnoho modelyuvannya. D.: RVV DNU. 16. P. 151-162 (In Ukrainian)

Christofides, N (1975) Graph Theory: An Algorithmic Approach. Academic Press Inc, Cambridge, Massachusetts, United States.

Garey, M. R.; Johnson, D. S. (1982) Computing machines and hard-to-solve tasks. M.: Mir. 1982. 416 p. (In Russian)

Vizing, V.G., Plesnevich, G.S. (1965) On the problem of minimal coloring of graph vertices. Sibirskij matematiceskij zurnal 6 (1) P. 234-236. (In Russian)

Stetsyuk, P.I., Lykhovyd, A.P. (2009) LP-oriented upper bounds for the weighted stability number of a graph. Cybern Syst Anal. 45. P.141–152.

Balansundaram, B., Butenko, S., Hicks, I.V. Clique relaxations in social network analysis: the maximum k-plex problem. Operations Research. 2011. Vol. 59, N 1. P. 133–142.

Gurobi Optimization Inc.: Gurobi Optimizer Reference Manual.

Fourer, R., Gay D., Kernighan B. (2003) AMPL, A Modeling Language for Mathematical Programming. Belmont: Duxburry Press. 517 p.

AMPL for research [Electronic resource]:

Nikolskyi, Yu. V., Pasichnyk, V. V., Shcherbina, Yu. M. (2007) Dyskretna matematyka. 368 p. (In Ukrainian)


  • There are currently no refbacks.