An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes

DOI10.1016/j.ipl.2014.09.027zbMath1302.68222MaRDI QIDQ477657

Dimitri Watel, Marc-Antoine Weisser, Cédric Bentz, Dominique Barith

Publication date: 9 December 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2014.09.027

zbMATH Keywords

algorithms; dynamic programming; combinatorial problems; parameterized complexity; directed Steiner tree

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)