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

DOI10.1016/J.IPL.2014.09.027zbMATH Open1302.68222OpenAlexW2005716729MaRDI QIDQ477657FDOQ477657

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

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

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)

Cites Work

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

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)