Multi-rooted greedy approximation of directed Steiner trees with applications
DOI10.1007/S00453-015-9973-1zbMATH Open1336.68295OpenAlexW2023646228MaRDI QIDQ262265FDOQ262265
Authors: Tomoya Hibi, Toshihiro Fujito 
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
Recommendations
- Multi-rooted greedy approximation of directed Steiner trees with applications
- A practical greedy approximation for the directed Steiner tree problem
- A practical greedy approximation for the directed Steiner tree problem
- scientific article; zbMATH DE number 1303557
- Approximation Algorithms for Directed Steiner Problems
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Cites Work
- A threshold of ln n for approximating set cover
- Reducibility among combinatorial problems
- 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
- How to trim a MST, a 2-approximation algorithm for minimum cost-tree cover
- Polylogarithmic inapproximability
- Title not available (Why is that?)
- Improved Approximations for the Steiner Tree Problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation Algorithms for Directed Steiner Problems
- Tighter Bounds for Graph Steiner Tree Approximation
- Steiner tree approximation via iterative randomized rounding
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- The Steiner tree problem on graphs: inapproximability results
Cited In (10)
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- On directed Steiner trees with multiple roots
- A practical greedy approximation for the directed Steiner tree problem
- A practical greedy approximation for the directed Steiner tree problem
- Directed Steiner trees with diffusion costs
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
- Approximation algorithm for the minimum directed tree cover
- Multi-rooted greedy approximation of directed Steiner trees with applications
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
This page was built for publication: Multi-rooted greedy approximation of directed Steiner trees with applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q262265)
