Light graphs with small routing cost
From MaRDI portal
Publication:4537619
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10)
Recommendations
- scientific article; zbMATH DE number 1303537
- Distributed approximation of minimum routing cost trees
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
- Minimum spanning tree with hop restrictions
- Approximation algorithms for some optimum communication spanning tree problems
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1775400 (Why is no real title available?)
- A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
- A fast algorithm for Steiner trees
- Approximation algorithms for some optimum communication spanning tree problems
- Approximation algorithms for the shortest total path length spanning tree problem
- Balancing minimum spanning trees and shortest-path trees
- Generalized Selection and Ranking: Sorted Matrices
- Graph spanners
- NP-completeness of minimum spanner problems
- On sparse spanners of weighted graphs
- On the minimum diameter spanning tree problem
- On the sum of all distances in a graph or digraph
- Optimum Communication Spanning Trees
- The complexity of designing a network with minimum diameter
- The complexity of the network design problem
- Time bounds for selection
- Worst-Case Analysis of Network Design Problem Heuristics
Cited in
(13)- Bounded-degree light approximate shortest-path trees in doubling metrics
- On the average distance of the hypercube tree
- Approximation algorithms for the optimal \(p\)-source communication spanning tree
- The greedy spanner is existentially optimal
- On thek-ary hypercube tree and its average distance
- On the minimum routing cost clustered tree problem
- Steiner shallow-light trees are exponentially lighter than spanning ones
- Light spanners for high dimensional norms via stochastic decompositions
- scientific article; zbMATH DE number 7378699 (Why is no real title available?)
- Network design for time-constrained delivery using subgraphs
- Lightweight paths in graphs
- Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs
- Light spanners
This page was built for publication: Light graphs with small routing cost
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4537619)
