.png){kind=icon}
Return
Solving the minimum labeling global cut problem by mathematical programming
.png){kind=icon}
OA
AI
DOI：10.1111/itor.13571.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
edge-labeled graphs
integer programming
branch-and-cut
polyhedral study
Journal
IF:
2.9
Papers:
1.8K
Citations:
3.7K
Organization
.png){kind=icon}
View more