Exact and Heuristic Solutions to the Connected k-Partitioning Problem - Université de Lorraine Access content directly
Conference Papers Year : 2020

Exact and Heuristic Solutions to the Connected k-Partitioning Problem

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.
Fichier principal
Vignette du fichier
codit20.pdf (254.36 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03795398 , version 1 (04-10-2022)

Identifiers

Cite

Patrick Healy, Pierre Laroche, Franc Marchetti, Sebastien Martin, Zsuzsanna Roka. Exact and Heuristic Solutions to the Connected k-Partitioning Problem. 2020 7th International Conference on Control, Decision and Information Technologies (CoDIT), Jun 2020, Prague, France. pp.1127-1132, ⟨10.1109/CoDIT49905.2020.9263884⟩. ⟨hal-03795398⟩
15 View
24 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More