Multi-rooted greedy approximation of directed Steiner trees with applications

DOI10.1007/S00453-015-9973-1zbMath1336.68295OpenAlexW2023646228MaRDI QIDQ262265

Toshihiro Fujito, Tomoya Hibi

Publication date: 29 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-9973-1

zbMATH Keywords

Steiner tree problemgreedy algorithmdirected graphsapproximation algorithmstree cover problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (3)

Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• The Steiner tree problem on graphs: inapproximability results
• Depth-first search and the vertex cover problem
• Approximating the weight of shallow Steiner trees
• New approximation algorithms for the Steiner tree problems
• Improved approximations for tour and tree covers
• An 11/6-approximation algorithm for the network Steiner problem
• The polymatroid Steiner problems
• A threshold of ln n for approximating set cover
• How to trim a MST
• Polylogarithmic inapproximability
• Improved Approximations for the Steiner Tree Problem
• Approximation Algorithms for Directed Steiner Problems
• Reducibility among Combinatorial Problems
• Tighter Bounds for Graph Steiner Tree Approximation
• Steiner Tree Approximation via Iterative Randomized Rounding

This page was built for publication: Multi-rooted greedy approximation of directed Steiner trees with applications