Balancing minimum spanning trees and shortest-path trees
From MaRDI portal
Publication:1899219
DOI10.1007/BF01294129zbMath0833.68096OpenAlexW2951475756MaRDI QIDQ1899219
Samir Khuller, Balaji Raghavachari, Neal E. Young
Publication date: 11 March 1996
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01294129
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (35)
STRONG CONNECTIVITY IN SENSOR NETWORKS WITH GIVEN NUMBER OF DIRECTIONAL ANTENNAE OF BOUNDED ANGLE ⋮ Light graphs with small routing cost ⋮ LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design ⋮ Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs ⋮ Incentive compatible and globally efficient position based routing for selfish reverse multicast in wireless sensor networks ⋮ Approximation Algorithms for Key Management in Secure Multicast ⋮ Terminal embeddings ⋮ Spanning trees and shortest paths in Monge graphs ⋮ On additive spanners in weighted graphs with local error ⋮ On the approximability of some Maximum Spanning Tree Problems ⋮ Advanced network connectivity features and zonal requirements in covering location problems ⋮ On the complexity of the cable-trench problem ⋮ Approximating capacitated tree-routings in networks ⋮ Competitive algorithms for the bicriteria \(k\)-server problem ⋮ Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology ⋮ Delay-related secondary objectives for rectilinear Steiner minimum trees. ⋮ Approximation to the Minimum Cost Edge Installation Problem ⋮ A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees ⋮ LP-based approximation algorithms for facility location in buy-at-bulk network design ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ Capacitated Vehicle Routing with Non-uniform Speeds ⋮ Approximating the \(k\)-splittable capacitated network design problem ⋮ Clifford algebra method for network expression, computation, and algorithm construction ⋮ Vehicle routing with subtours ⋮ On the approximation of the generalized capacitated tree-routing problem ⋮ MIXED SPANNING TREES IN THEORY AND PRACTICE ⋮ The cable trench problem: Combining the shortest path and minimum spanning tree problems ⋮ Capacitated Vehicle Routing with Nonuniform Speeds ⋮ The non-approximability of bicriteria network design problems ⋮ Minimizing the sum of distances to a server in a constraint network ⋮ Approximating the weight of shallow Steiner trees ⋮ Electrical flows over spanning trees ⋮ Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time ⋮ Reducing the diameter of a unit disk graph via node addition ⋮ An improved approximation algorithm for the uniform cost-distance Steiner tree problem
Cites Work
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
- On sparse spanners of weighted graphs
- A sparse graph almost as good as the complete graph on points in \(k\) dimensions
- There are planar graphs almost as good as the complete graph
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- An Optimal Synchronizer for the Hypercube
- Routing to Multiple Destinations in Computer Networks
This page was built for publication: Balancing minimum spanning trees and shortest-path trees
