Approximating the weight of shallow Steiner trees
From MaRDI portal
Publication:1296580
DOI10.1016/S0166-218X(99)00111-0zbMath0931.68077WikidataQ126382960 ScholiaQ126382960MaRDI QIDQ1296580
Publication date: 7 February 2000
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items (29)
Bounded Degree Group Steiner Tree Problems ⋮ $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ Finding bounded diameter minimum spanning tree in general graphs ⋮ On the bounded-hop MST problem on random Euclidean instances ⋮ Efficient offline algorithms for the bicriteria \(k\)-server problem and online applications ⋮ Embedding rectilinear Steiner trees with length restrictions ⋮ The Rectilinear Steiner Tree Problem with Given Topology and Length Restrictions ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ Improved approximation algorithms for directed Steiner forest ⋮ The lower and upper forcing geodetic numbers of block--cactus graphs ⋮ A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks ⋮ Algorithms for the minimum diameter terminal Steiner tree problem ⋮ Approximating \(k\)-hop minimum-spanning trees ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ Bounded-hops power assignment in ad hoc wireless networks ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ On the characterization of the domination of a diameter-constrained network reliability model ⋮ The lower and upper forcing geodetic numbers of completen-partite graphs,n-dimensional meshes and tori ⋮ Delay-constrained minimum shortest path trees and related problems ⋮ Delay-constrained minimum shortest path trees and related problems ⋮ Inapproximability of survivable networks ⋮ Differential approximation of NP-hard problems with equal size feasible solutions ⋮ Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems ⋮ Approximating fault-tolerant group-Steiner problems ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ A greedy approximation algorithm for the group Steiner problem ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Tight bounds on subexponential time approximation of set cover and related problems ⋮ Multi-rooted greedy approximation of directed Steiner trees with applications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Generalized submodular cover problems and applications
- An analysis of the greedy algorithm for the submodular set covering problem
- Balancing minimum spanning trees and shortest-path trees
- Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
- A Greedy Heuristic for the Set-Covering Problem
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Approximation Schemes for the Restricted Shortest Path Problem
- Bicriteria Network Design Problems
- On the hardness of approximating minimization problems
- Routing to Multiple Destinations in Computer Networks
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Many birds with one stone
- The network inhibition problem
This page was built for publication: Approximating the weight of shallow Steiner trees
