Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation

Meike Hatzel; Lars Jaffke; Paloma Thomé de Lima; Tomáš Masařík; Marcin Pilipczuk; Roohani Sharma; Manuel Sorge

doi:10.1137/1.9781611977554.ch123

Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation

Meike Hatzel
, Lars Jaffke
, Paloma Thomé de Lima
, Tomáš Masařík
, Marcin Pilipczuk
, Roohani Sharma
, Manuel Sorge

Algorithms

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

Originalsprog	Engelsk
Titel	Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
Forlag	Society for Industrial and Applied Mathematics
Publikationsdato	2023
Sider	3229 - 3244
DOI	https://doi.org/10.1137/1.9781611977554.ch123
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

Adgang til dokumentet

10.1137/1.9781611977554.ch123

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

Citationsformater

Hatzel, M., Jaffke, L., Thomé de Lima, P., Masařík, T., Pilipczuk, M., Sharma, R., & Sorge, M. (2023). Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. I Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023) (s. 3229 - 3244). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977554.ch123

@inproceedings{14c9e44edd7c47d98d4e58e4995cf658,

title = "Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation",

author = "Meike Hatzel and Lars Jaffke and \{Thom{\'e} de Lima\}, Paloma and Tom{\'a}{\v s} Masa{\v r}{\'i}k and Marcin Pilipczuk and Roohani Sharma and Manuel Sorge",

year = "2023",

doi = "10.1137/1.9781611977554.ch123",

language = "English",

pages = "3229 -- 3244",

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

}

Hatzel, M, Jaffke, L, Thomé de Lima, P, Masařík, T, Pilipczuk, M, Sharma, R & Sorge, M 2023, Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. i Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Society for Industrial and Applied Mathematics, s. 3229 - 3244, Symposium on Discrete Algorithms, Firenze, Italien, 22/01/2023. https://doi.org/10.1137/1.9781611977554.ch123

Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. / Hatzel, Meike; Jaffke, Lars; Thomé de Lima, Paloma et al.
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Society for Industrial and Applied Mathematics, 2023. s. 3229 - 3244.

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation

AU - Hatzel, Meike

AU - Jaffke, Lars

AU - Thomé de Lima, Paloma

AU - Masařík, Tomáš

AU - Pilipczuk, Marcin

AU - Sharma, Roohani

AU - Sorge, Manuel

N1 - Conference code: 34

PY - 2023

Y1 - 2023

U2 - 10.1137/1.9781611977554.ch123

DO - 10.1137/1.9781611977554.ch123

M3 - Article in proceedings

SP - 3229

EP - 3244

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 -

Hatzel M, Jaffke L, Thomé de Lima P, Masařík T, Pilipczuk M, Sharma R et al. Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. I Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Society for Industrial and Applied Mathematics. 2023. s. 3229 - 3244 doi: 10.1137/1.9781611977554.ch123