Exact and Heuristic Solutions to the Connected k-Partitioning Problem

Patrick Healy, Pierre Laroche, Franc Marchetti, Sebastien Martin, Zsuzsanna Roka

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publication7th International Conference on Control, Decision and Information Technologies, CoDIT 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1127-1132
Number of pages6
ISBN (Electronic)9781728159539
DOIs
Publication statusPublished - 29 Jun 2020
Event7th International Conference on Control, Decision and Information Technologies, CoDIT 2020 - Prague, Czech Republic
Duration: 29 Jun 20202 Jul 2020

Publication series

Name7th International Conference on Control, Decision and Information Technologies, CoDIT 2020

Conference

Conference7th International Conference on Control, Decision and Information Technologies, CoDIT 2020
Country/TerritoryCzech Republic
CityPrague
Period29/06/202/07/20

Fingerprint

Dive into the research topics of 'Exact and Heuristic Solutions to the Connected k-Partitioning Problem'. Together they form a unique fingerprint.

Cite this