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

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

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

}

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

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

ER -

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

Abstract

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater