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

DOI10.1016/J.IPL.2014.09.027MaRDI QIDQ477657zbMATH OpenOpenAlexFDO

Authors Dimitri Watel, Marc-Antoine Weisser, Cédric Bentz, D. Barth

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 programmingparameterized complexitycombinatorial problemsdirected Steiner tree

Mathematics Subject Classification ID

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

Recommendations

• A practical greedy approximation for the directed Steiner tree problem
• A practical greedy approximation for the directed Steiner tree problem
• Approximating directed Steiner problems via tree embedding
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• Directed Steiner trees with diffusion costs
• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
• Computing optimal Steiner trees in polynomial space
• Faster Steiner Tree Computation in Polynomial-Space
• Improved approximation algorithms for directed Steiner forest
• Approximation Algorithms for Directed Steiner Problems

Cites work

• scientific article; zbMATH DE number 3900794 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• A note on distributed multicast routing in point-to-point networks
• Analytic combinatorics
• Computing optimal Steiner trees in polynomial space
• Directed Steiner tree with branching constraint
• Dynamic programming for minimum Steiner trees
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Fourier meets M\"{o}bius: fast subset convolution
• Spanning spiders and light-splitting switches
• Steiner tree problems in telecommunications
• The steiner problem in graphs

Cited in

(4)

• Steiner problems with limited number of branching nodes
• Directed Steiner tree with branching constraint
• On the edge capacitated Steiner tree problem
• Directed Steiner trees with diffusion costs

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

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