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.68222OpenAlexW2005716729MaRDI QIDQ477657

Dimitri Watel, Cédric Bentz, Marc-Antoine Weisser, 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

algorithmsdynamic programmingcombinatorial problemsparameterized complexitydirected Steiner tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

On the edge capacitated Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spanning spiders and light-splitting switches
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Computing optimal Steiner trees in polynomial space
• Dynamic programming for minimum Steiner trees
• Directed Steiner Tree with Branching Constraint
• Fourier meets M\"{o}bius: fast subset convolution
• The steiner problem in graphs
• A note on distributed multicast routing in point-to-point networks

This page was built for publication: An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes