TY - GEN
T1 - Exact and Heuristic Solutions to the Connected k-Partitioning Problem
AU - Healy, Patrick
AU - Laroche, Pierre
AU - Marchetti, Franc
AU - Martin, Sebastien
AU - Roka, Zsuzsanna
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/6/29
Y1 - 2020/6/29
N2 - We study the problem of partitioning a graph into k connected components, which may also be referred to as the maximum k-cutset problem. Firstly, we present an exact algorithm and a variant, both implemented as integer linear programming (ILP) models. We then present a heuristic approach that will be seen to be extremely competitive with the exact algorithm for the ranges of graph under consideration.
AB - We study the problem of partitioning a graph into k connected components, which may also be referred to as the maximum k-cutset problem. Firstly, we present an exact algorithm and a variant, both implemented as integer linear programming (ILP) models. We then present a heuristic approach that will be seen to be extremely competitive with the exact algorithm for the ranges of graph under consideration.
UR - http://www.scopus.com/inward/record.url?scp=85098290573&partnerID=8YFLogxK
U2 - 10.1109/CoDIT49905.2020.9263884
DO - 10.1109/CoDIT49905.2020.9263884
M3 - Conference contribution
AN - SCOPUS:85098290573
T3 - 7th International Conference on Control, Decision and Information Technologies, CoDIT 2020
SP - 1127
EP - 1132
BT - 7th International Conference on Control, Decision and Information Technologies, CoDIT 2020
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 7th International Conference on Control, Decision and Information Technologies, CoDIT 2020
Y2 - 29 June 2020 through 2 July 2020
ER -