Solving the minimum labeling global cut problem by mathematical programming

doi:10.1111/itor.13571

2024-11-16

Victor José de Sousa Koehler

Thiago Gouveia

Gilberto Farias de Sousa Filho *

DOI：10.1111/itor.13571

原文链接

原文求助

摘要

En 中文

An edge-labeled graph (ELG) G=(V,E,L)$G=(V,E,L)$ is a graph such that V$V$ is the set of vertices, E$E$ is the set of edges, L$L$ is the set of labels (colors), and each edge e is an element of E$e \in E$ has a label associated. Given an ELG G=(V,E,L)$G=(V,E,L)$, the goal of the minimum labeling global cut problem (MLGCP) is to find a subset L 'subset of L$L<^>{\prime } \subseteq L$ such that the removal of all edges with labels in L '$L<^>{\prime }$ disconnects G$G$ and |L '|$|L<^>{\prime }|$ is minimum. This work proposes three new mathematical formulations for the MLGCP, namely PART, VC, and TE as well as branch-and-cut algorithms to solve them. Additionally, a theoretical study was carried out on the MLGCP input graph, leading to the concept of chromatic closure, used in preprocessing algorithms for this model PART. Finally, a comprehensive polyhedral investigation of the model is performed. The computational experiments showed that the PART$PART$ model, adopting the chromatic closure concept and its branch-and-cut algorithm, can solve small to average-sized instances in reasonable times.

Keyword:

edge-labeled graphs

integer programming

branch-and-cut

polyhedral study