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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• 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 (1)

• On the edge capacitated Steiner tree problem

Recommendations

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

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)