A practical greedy approximation for the directed Steiner tree problem

DOI10.1007/S10878-016-0074-0MaRDI QIDQ346528zbMATH OpenOpenAlexFDO

Authors Dimitri Watel, Marc-Antoine Weisser

Publication date 29 November 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-016-0074-0

zbMATH Keywords

approximation algorithmgreedy algorithmdirected Steiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A practical greedy approximation for the directed Steiner tree problem
• Multi-rooted greedy approximation of directed Steiner trees with applications
• Multi-rooted greedy approximation of directed Steiner trees with applications
• scientific article; zbMATH DE number 1303557
• Approximation Algorithms for Directed Steiner Problems

Cites work

• scientific article; zbMATH DE number 3495588 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 2209521 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A distributed dual ascent algorithm for Steiner problems in multicast routing
• A dual ascent approach for steiner tree problems on a directed graph
• A fast algorithm for Steiner trees
• A note on distributed multicast routing in point-to-point networks
• A practical greedy approximation for the directed Steiner tree problem
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• A threshold of ln n for approximating set cover
• An 11/6-approximation algorithm for the network Steiner problem
• An improved approximation scheme for the Group Steiner Problem
• Approximation Algorithms for Directed Steiner Problems
• Contraction-based Steiner tree approximations in practice
• Dual heuristics on the exact solution of large Steiner problems
• Fast local search for Steiner trees in graphs
• Polylogarithmic inapproximability
• Steiner tree approximation via iterative randomized rounding
• Steiner tree problems in telecommunications

Cited in

(10)

• Multi-rooted greedy approximation of directed Steiner trees with applications
• Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
• An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
• A practical greedy approximation for the directed Steiner tree problem
• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
• Heuristic and exact algorithms for minimum-weight non-spanning arborescences
• Multi-rooted greedy approximation of directed Steiner trees with applications
• A linear programming based approach to the Steiner tree problem with a fixed number of terminals
• Linear Programming Hierarchies Suffice for Directed Steiner Tree
• Navigational guidance -- a deep learning approach

Describes a project that uses

Uses Software

• Algorithm 97
• SteinLib

This page was built for publication: A practical greedy approximation for the directed Steiner tree problem

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