Квадратична задача для максимального k-плекса в неорiєнтованому графi
Loading...
Date
2017
Authors
Стецюк, Петро
Бардадим, Тамара
Ляшко, Володимир
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
У статтi сформульовано квадратичну оптимiзацiйну
задачу для знаходження максимального k-плекса у неорiєнтованому графi. Показано, що квадратичну задачу можно отримати з
вiдомої лiнiйної булевої задачi для максимального k-плекса. Наведено два сiмейства функцiонально надлишкових квадратичних
обмежень, якi отримано за допомогою обмежень булевої задачi.
The quadratic optimization problem of finding maximum k-plex in undirected graph is formulated. It is demonstrated that the quadratic problem can be obtained from well-known linear Boolean problem for maximum k-plex. Two families of functionally superfluous quadratic constraints obtained from Boolean problem constraints are reported.
The quadratic optimization problem of finding maximum k-plex in undirected graph is formulated. It is demonstrated that the quadratic problem can be obtained from well-known linear Boolean problem for maximum k-plex. Two families of functionally superfluous quadratic constraints obtained from Boolean problem constraints are reported.
Description
Keywords
максимальний k-плекс, квадратична оптимiзацiйна задача, задача булевого лiнiйного програмування, функцiонально надлишковi обмеження, стаття, maximum k-plex, quadratic optimization problem, Boolean linear programming problem, superfluous constraint
Citation
Стецюк П. Квадратична задача для максимального k-плекса в неорiєнтованому графi / П. I. Стецюк, Т. О. Бардадим, В. I. Ляшко // Журнал обчислювальної та прикладної математики. - 2017. - № 1 (124). - С. 80-87.