Abstract
e study a generalization of the classic GLOBAL MIN-CUT problem, called GLOBAL LABEL MIN-CUT (or sometimes GLOBAL HEDGE MIN-CUT): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost.
Original language | English |
---|---|
Title of host publication | Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023) |
Number of pages | 13 |
Publisher | Society for Industrial and Applied Mathematics |
Publication date | 2023 |
Pages | 290-303 |
ISBN (Electronic) | 978-1-61197-755-4 |
DOIs | |
Publication status | Published - 2023 |
Keywords
- Global Min-Cut Problem
- Labeled Edges
- Minimum Cut Cost
- Graph Partitioning
- Hedge Min-Cut