Light graphs with small routing cost
DOI10.1002/NET.10019zbMATH Open1028.90075OpenAlexW1975752629MaRDI QIDQ4537619FDOQ4537619
Authors: Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang 
Publication date: 1 July 2002
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.10019
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Generalized Selection and Ranking: Sorted Matrices
- On the sum of all distances in a graph or digraph
- On sparse spanners of weighted graphs
- Graph spanners
- Approximation algorithms for the shortest total path length spanning tree problem
- The complexity of the network design problem
- Time bounds for selection
- Approximation algorithms for some optimum communication spanning tree problems
- Optimum Communication Spanning Trees
- Worst-Case Analysis of Network Design Problem Heuristics
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
- A fast algorithm for Steiner trees
- On the minimum diameter spanning tree problem
- The complexity of designing a network with minimum diameter
- NP-completeness of minimum spanner problems
- A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees
- Balancing minimum spanning trees and shortest-path trees
Cited In (13)
- Steiner shallow-light trees are exponentially lighter than spanning ones
- Network design for time-constrained delivery using subgraphs
- On thek-ary hypercube tree and its average distance
- Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs
- Bounded-degree light approximate shortest-path trees in doubling metrics
- On the minimum routing cost clustered tree problem
- Light spanners
- Title not available (Why is that?)
- Lightweight paths in graphs
- The greedy spanner is existentially optimal
- On the average distance of the hypercube tree
- Approximation algorithms for the optimal \(p\)-source communication spanning tree
- Light spanners for high dimensional norms via stochastic decompositions
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)
