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

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
Antal sider	13
Forlag	Society for Industrial and Applied Mathematics
Publikationsdato	2023
Sider	290-303
ISBN (Elektronisk)	978-1-61197-755-4
DOI	https://doi.org/10.1137/1.9781611977554.ch12
Status	Udgivet - 2023
Begivenhed	Symposium on Discrete Algorithms - Grand Hotel Mediterraneo, Firenze, Italien Varighed: 22 jan. 2023 → 25 jan. 2023 Konferencens nummer: 34 https://www.siam.org/conferences-events/past-event-archive/soda23/?utm

Symposium

Symposium	Symposium on Discrete Algorithms
Nummer	34
Lokation	Grand Hotel Mediterraneo
Land/Område	Italien
By	Firenze
Periode	22/01/2023 → 25/01/2023
Internetadresse	https://www.siam.org/conferences-events/past-event-archive/soda23/?utm

Emneord

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

Adgang til dokumentet

10.1137/1.9781611977554.ch12

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

Citationsformater

@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. s. 290-303.

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater