Fixed-parameter tractability of \textsc{Directed Multicut} with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation

DOI10.1137/1.9781611977554.CH123MaRDI QIDQ6538653zbMATH OpenFDO

Authors Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomáš Masařík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge

Publication date 14 May 2024

Full work available at URL https://doi.org/10.1137/1.9781611977554.CH123

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset

Cited in

(5)

• Directed flow-augmentation
• Flow-augmentation. I: Directed graphs
• Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
• Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
• A parameterized study of secluded structures in directed graphs

This page was built for publication: Fixed-parameter tractability of \textsc{Directed Multicut} with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6538653)