Exact and Heuristic Solutions to the Connected k-Partitioning Problem - Université de Lorraine Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Exact and Heuristic Solutions to the Connected k-Partitioning Problem

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

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⟩
13 Consultations
21 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More