A tight quasi-polynomial bound for Global Label Min-Cut

Lars Jaffke, Paloma Thomé de Lima, Tomáš Masařík, Marcin Pilipczuk, Uéverton Souza

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

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.
OriginalsprogEngelsk
TitelAnnual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
Antal sider13
ForlagSociety for Industrial and Applied Mathematics
Publikationsdato2023
Sider290-303
ISBN (Elektronisk)978-1-61197-755-4
DOI
StatusUdgivet - 2023

Fingeraftryk

Dyk ned i forskningsemnerne om 'A tight quasi-polynomial bound for Global Label Min-Cut'. Sammen danner de et unikt fingeraftryk.

Citationsformater