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

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

doi:10.1137/1.9781611977554.ch12

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

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

Algorithms

University of Warsaw
University of Bergen
Federal Fluminense University

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-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.

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	https://doi.org/10.1137/1.9781611977554.ch12
Publication status	Published - 2023
Event	Symposium on Discrete Algorithms - Grand Hotel Mediterraneo, Firenze, Italy Duration: 22 Jan 2023 → 25 Jan 2023 Conference number: 34 https://www.siam.org/conferences-events/past-event-archive/soda23/?utm

Symposium

Symposium	Symposium on Discrete Algorithms
Number	34
Location	Grand Hotel Mediterraneo
Country/Territory	Italy
City	Firenze
Period	22/01/2023 → 25/01/2023
Internet address	https://www.siam.org/conferences-events/past-event-archive/soda23/?utm

Keywords

Global Min-Cut Problem
Labeled Edges
Minimum Cut Cost
Graph Partitioning
Hedge Min-Cut

Access to Document

10.1137/1.9781611977554.ch12

https://epubs.siam.org/doi/reader/10.1137/1.9781611977554.ch12

Cite this

@inproceedings{83fe73233b234bef81c582cf23aaae58,

title = "A tight quasi-polynomial bound for Global Label Min-Cut",

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.",

keywords = "Global Min-Cut Problem, Labeled Edges, Minimum Cut Cost, Graph Partitioning, Hedge Min-Cut, Global Min-Cut Problem, Labeled Edges, Minimum Cut Cost, Graph Partitioning, Hedge Min-Cut",

author = "Lars Jaffke and \{Thom{\'e} de Lima\}, Paloma and Tom{\'a}{\v s} Masa{\v r}{\'i}k and Marcin Pilipczuk and U{\'e}verton Souza",

year = "2023",

doi = "10.1137/1.9781611977554.ch12",

language = "English",

pages = "290--303",

booktitle = "Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)",

publisher = "Society for Industrial and Applied Mathematics",

address = "United States",

note = "Symposium on Discrete Algorithms, SODA ; Conference date: 22-01-2023 Through 25-01-2023",

url = "https://www.siam.org/conferences-events/past-event-archive/soda23/?utm",

}

A tight quasi-polynomial bound for Global Label Min-Cut. / Jaffke, Lars; Thomé de Lima, Paloma; Masařík, Tomáš et al.
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Society for Industrial and Applied Mathematics, 2023. p. 290-303.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

TY - GEN

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

AU - Jaffke, Lars

AU - Thomé de Lima, Paloma

AU - Masařík, Tomáš

AU - Pilipczuk, Marcin

AU - Souza, Uéverton

N1 - Conference code: 34

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - Global Min-Cut Problem

KW - Labeled Edges

KW - Minimum Cut Cost

KW - Graph Partitioning

KW - Hedge Min-Cut

KW - Global Min-Cut Problem

KW - Labeled Edges

KW - Minimum Cut Cost

KW - Graph Partitioning

KW - Hedge Min-Cut

U2 - 10.1137/1.9781611977554.ch12

DO - 10.1137/1.9781611977554.ch12

M3 - Article in proceedings

SP - 290

EP - 303

BT - Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)

PB - Society for Industrial and Applied Mathematics

T2 - Symposium on Discrete Algorithms

Y2 - 22 January 2023 through 25 January 2023

ER -

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

Abstract

Symposium

Keywords

Access to Document

Fingerprint

Cite this