Fixed-parameter tractability of multicut in directed acyclic graphs

DOI10.1137/120904202MaRDI QIDQ6829944zbMATH OpenFDO

Authors Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström

Publication date 27 November 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/66096/1/WRAP_120904202.pdf

zbMATH Keywords

directed acyclic graphfixed-parameter tractabilityimportant separatorsmulticutshadow removal

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Cited in

(2)

• On the parameterized complexity of symmetric directed multicut
• Towards transitive-free digraphs

This page was built for publication: Fixed-parameter tractability of multicut in directed acyclic graphs

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