A tight quasi-polynomial bound for Global Label Min-Cut
- Lars Jaffke,
- ,
- Tomáš Masařík,
- Marcin Pilipczuk,
- Uéverton Souza
- University of Warsaw,
- University of Bergen,
- ,
- Federal Fluminense University
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-review
Open access
Publication Information
Output type
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-reviewOriginal language
EnglishPages from-to (Number of pages)
Pages 290-303 (13 pages)Publication milestones
- Published - 2023
Publication status
Published - 2023
Publisher
Society for Industrial and Applied Mathematics, United StatesISBN (Electronic)
978-1-61197-755-4Publication IDs
- Scopus: 85168817812
Host publication title
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)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.
Publication metrics
PlumX, opens in new tab
Citations
11
Access to documents
Related Event
Title
Symposium on Discrete Algorithms
Event type
SymposiumDegree of recognition
International eventDate
22/01/2023 - 25/01/2023Location
Grand Hotel MediterraneoFirenzeItaly