HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Exact and Heuristic Algorithms for the Maximum k-Cutset Problem

Abstract : Given a connected unit-weighted graph, we study the Maximum k-Cutset Problem, consisting in cutting a graph into k vertex-disjoint sub-graphs, each connected. We propose some exact and heuristic solutions to solve the problem. The first Integer Linear Program is based on a combination of a cut model and an assignment model. The two other Integer Linear Programs are based on the existence of spanning trees. The presented heuristics are clustering algorithms using local search. Experiments have been run on randomly generated instances and a specific set of instances. We observe that the running times are related to the tree-arboricity of graphs. The tree-arboricity is also used to ensure the optimality of solutions found by our heuristics.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.univ-lorraine.fr/hal-02264750
Contributor : Zsuzsanna Roka Connect in order to contact the contributor
Submitted on : Wednesday, August 7, 2019 - 2:54:43 PM
Last modification on : Monday, November 15, 2021 - 1:10:06 PM
Long-term archiving on: : Thursday, January 9, 2020 - 1:35:35 AM

File

MaxKCutsetHAL.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02264750, version 1

Collections

Citation

Patrick Healy, Pierre Laroche, Franc Marchetti, Sébastien Martin, Zsuzsanna Roka. Exact and Heuristic Algorithms for the Maximum k-Cutset Problem. 2019. ⟨hal-02264750⟩

Share

Metrics

Record views

60

Files downloads

103