Optimization problems for the maximum k-plex / Stetsyuk, / Khomiak, / Blokhin, / Suprun. (2022)

English  Cybernetics and Systems Analysis   /     Issue (2022, 58 (4))

Stetsyuk P.I., Khomiak O.M., Blokhin Y.A., Suprun A.A.
Optimization problems for the maximum k-plex

The quadratic optimization problem for finding the maximum k-plex in an undirected graph is constructed. Two families of superfluous quadratic constraints obtained by means of constraints of the Boolean linear programming problem for the maximum k-plex are presented. The influence of superfluous constraints on the improvement of the accuracy of Lagrangian dual bounds for the objective function of the quadratic problem is investigated. The algorithm for searching all the maximum k-plexes is developed and the results of test experiments for its implementation using the GLPK (GNU Linear Programming Kit) software package are presented. © 2022, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: Boolean linear programming problem, Lagrangian dual bound, maximum clique, maximum k-plex, quadratic optimization problem, superfluous constraint, Constrained optimization, Lagrange multipliers, Open source software, Quadratic programming, Software testing, Undirected graphs, Boolean linear programming problem, Dual bound, Lagrangian dual, Lagrangian dual bound, Linear programming problem, Maximum clique, Maximum k-plex, Optimization problems, Quadratic optimization problems, Superfluous constraint, Linear programming

Download publication will be available after 09/01/2024 р., in 188 days

Stetsyuk P.I., Khomiak O.M., Blokhin Y.A., Suprun A.A. (2022). Optimization problems for the maximum k-plex. Cybernetics and Systems Analysis, 58 (4), 46–58. doi: https://doi.org/10.1007/s10559-022-00488-5 http://jnas.nbuv.gov.ua/article/UJRN-0001335519 [In Ukrainian].


Institute of Information Technologies of VNLU

+38 (044) 525-36-24
Ukraine, 03039, Kyiv, Holosiivskyi Ave, 3, room 209