Light graphs with small routing cost

DOI10.1002/net.10019zbMath1028.90075OpenAlexW1975752629MaRDI QIDQ4537619

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

zbMATH Keywords

network designapproximation algorithmsspanning trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the minimum routing cost clustered tree problem ⋮ Approximation algorithms for the optimal \(p\)-source communication spanning tree ⋮ Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs ⋮ Network design for time-constrained delivery using subgraphs ⋮ Unnamed Item ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ On the average distance of the hypercube tree ⋮ The Greedy Spanner Is Existentially Optimal ⋮ On thek-ary hypercube tree and its average distance ⋮ Light Spanners ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ Light spanners for high dimensional norms via stochastic decompositions

Cites Work

• Unnamed Item
• Unnamed Item
• On the minimum diameter spanning tree problem
• A fast algorithm for Steiner trees
• On sparse spanners of weighted graphs
• NP-completeness of minimum spanner problems
• Time bounds for selection
• 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
• Optimum Communication Spanning Trees
• Generalized Selection and Ranking: Sorted Matrices
• On the sum of all distances in a graph or digraph
• Graph spanners
• The complexity of designing a network with minimum diameter
• Worst-Case Analysis of Network Design Problem Heuristics
• The complexity of the network design problem
• A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees