Concepedia

Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem

Mattia D’Emidio, Luca Forlizzi, Daniele Frigioni, Stefano Leucci, Guido Proietti

Journal of Combinatorial Optimization · 2019 · 23 citations · 15 references

Open access

Concepts

ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationApproximation AlgorithmsCombinatorial OptimizationComputational ComplexityParameterized AlgorithmsShortest Path AlgorithmsApproximation Algorithms For Shortest PathsFixed-parameter TractabilityShortest Path ProblemsShortest Path TreesTree Algorithms

References

15

A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem

Naveen Garg, Goran Konjevod, R. Ravi · Journal of Algorithms · 2000 · 281 citations

Computing, Computer Science, Mathematics +15

Steiner Tree Approximation via Iterative Randomized Rounding

Jarosław Byrka, Fabrizio Grandoni, Laura Sanità · Journal of the ACM · 2013 · 280 citations · Full text

Natural Sciences, Computer Science, Algorithms +13

Fourier meets möbius: fast subset convolution

Andreas Björklund, Thore Husfeldt, Petteri Kaski et al. · 2007 · 278 citations

Computing, Computer Science, Mathematics +9

Polylogarithmic inapproximability

Eran Halperin, Robert Krauthgamer · 2003 · 229 citations

Computing, Computer Science, Mathematics +17

Generalized network design problems

Corinne Feremans, Martine Labbé, Gilbert Laporte · European Journal of Operational Research · 2003 · 104 citations

Natural Sciences, Computer Science, Computer Networks +11