An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
type: Item
instance of: scholarly article
title: An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
zbMATH Open document ID: 1302.68222
author: Dimitri Watel
author: Marc-Antoine Weisser
author: Cédric Bentz
author: D. Barth
published in: Information Processing Letters
publication date: 2014-12-09T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6378669
zbMATH Keywords: directed Steiner tree
zbMATH Keywords: parameterized complexity
zbMATH Keywords: dynamic programming
zbMATH Keywords: algorithms
zbMATH Keywords: combinatorial problems
MaRDI profile type: Publication
full work available at URL: j.ipl.2014.09.027
OpenAlex ID: W2005716729
cites work: Fourier meets M\"{o}bius: fast subset convolution
cites work: The steiner problem in graphs
cites work: Q3549563
cites work: Computing optimal Steiner trees in polynomial space
cites work: Dynamic programming for minimum Steiner trees
cites work: Spanning spiders and light-splitting switches
cites work: Q4142699
cites work: Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
cites work: A note on distributed multicast routing in point-to-point networks
cites work: Q3679220
cites work: Q5294062
cites work: Directed Steiner Tree with Branching Constraint
DOI: 10.1016/J.IPL.2014.09.027
Recommended article: A Practical Greedy Approximation for the Directed Steiner Tree Problem
Recommended article: A practical greedy approximation for the directed Steiner tree problem
Recommended article: Approximating Directed Steiner Problems via Tree Embedding
Recommended article: A series of approximation algorithms for the acyclic directed Steiner tree problem
Recommended article: Directed Steiner trees with diffusion costs
Recommended article: Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
Recommended article: Computing optimal Steiner trees in polynomial space
Recommended article: Faster Steiner Tree Computation in Polynomial-Space
Recommended article: Improved approximation algorithms for directed Steiner forest
Recommended article: Approximation Algorithms for Directed Steiner Problems
description: scientific article; zbMATH DE number 6378669