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

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

Original language	English
Title of host publication	Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
Publisher	Society for Industrial and Applied Mathematics
Publication date	2023
Pages	3229 - 3244
DOIs	https://doi.org/10.1137/1.9781611977554.ch123
Publication status	Published - 2023

Access to Document

10.1137/1.9781611977554.ch123

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

Cite this

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. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023) (pp. 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",

}

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. in Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Society for Industrial and Applied Mathematics, pp. 3229 - 3244. 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. p. 3229 - 3244.

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

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

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. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Society for Industrial and Applied Mathematics. 2023. p. 3229 - 3244 doi: 10.1137/1.9781611977554.ch123