Approximating the weight of shallow Steiner trees
From MaRDI portal
Publication:1296580
DOI10.1016/S0166-218X(99)00111-0zbMATH Open0931.68077WikidataQ126382960 ScholiaQ126382960MaRDI QIDQ1296580FDOQ1296580
Publication date: 7 February 2000
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- A Greedy Heuristic for the Set-Covering Problem
- Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
- Approximation Schemes for the Restricted Shortest Path Problem
- Bicriteria Network Design 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
- Routing to Multiple Destinations in Computer Networks
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- On the hardness of approximating minimization problems
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Many birds with one stone
- The network inhibition problem
- Balancing minimum spanning trees and shortest-path trees
Cited In (31)
- Multi-rooted greedy approximation of directed Steiner trees with applications
- Low-light trees, and tight lower bounds for Euclidean spanners
- Delay-constrained minimum shortest path trees and related problems
- Delay-constrained minimum shortest path trees and related problems
- Approximating \(k\)-hop minimum-spanning trees
- The lower and upper forcing geodetic numbers of block--cactus graphs
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- Improved approximation algorithms for directed Steiner forest
- Inapproximability of survivable networks
- Efficient offline algorithms for the bicriteria \(k\)-server problem and online applications
- Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems
- The Rectilinear Steiner Tree Problem with Given Topology and Length Restrictions
- Bounded-hops power assignment in ad hoc wireless networks
- A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
- A greedy approximation algorithm for the group Steiner problem
- Embedding rectilinear Steiner trees with length restrictions
- Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k,2)-Subgraph
- Algorithms for the minimum diameter terminal Steiner tree problem
- Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems
- Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees
- Tight bounds on subexponential time approximation of set cover and related problems
- Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones
- Approximating fault-tolerant group-Steiner problems
- On the bounded-hop MST problem on random Euclidean instances
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- Bounded Degree Group Steiner Tree Problems
- Finding bounded diameter minimum spanning tree in general graphs
- On the characterization of the domination of a diameter-constrained network reliability model
- Differential approximation of NP-hard problems with equal size feasible solutions
- The lower and upper forcing geodetic numbers of completen-partite graphs,n-dimensional meshes and tori
- $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: Approximating the weight of shallow Steiner trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1296580)
