Multi-rooted greedy approximation of directed Steiner trees with applications

DOI10.1007/S00453-015-9973-1MaRDI QIDQ262265zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

greedy algorithmapproximation algorithmsdirected graphsSteiner tree problemtree 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)

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

Cites work

• scientific article; zbMATH DE number 1305468 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 2119644 (Why is no real title available?)
• 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
• Approximating the weight of shallow Steiner trees
• Approximation Algorithms for Directed Steiner Problems
• Depth-first search and the vertex cover problem
• How to trim a MST, a 2-approximation algorithm for minimum cost-tree cover
• Improved Approximations for the Steiner Tree Problem
• Improved approximations for tour and tree covers
• New approximation algorithms for the Steiner tree problems
• Polylogarithmic inapproximability
• Reducibility among combinatorial problems
• Steiner tree approximation via iterative randomized rounding
• The Steiner tree problem on graphs: inapproximability results
• The polymatroid Steiner problems
• Tighter Bounds for Graph Steiner Tree Approximation

Cited in

(10)

• $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
• 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
• Directed Steiner trees with diffusion costs
• A practical greedy approximation for the directed Steiner tree problem
• 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

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)