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

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

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-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 languageEnglish
Title of host publicationAnnual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
Number of pages13
PublisherSociety for Industrial and Applied Mathematics
Publication date2023
Pages290-303
ISBN (Electronic)978-1-61197-755-4
DOIs
Publication statusPublished - 2023

Keywords

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

Fingerprint

Dive into the research topics of 'A tight quasi-polynomial bound for Global Label Min-Cut'. Together they form a unique fingerprint.

Cite this