A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees

DOI10.1006/jagm.1997.0862zbMath0895.68107arXivcs/0205050OpenAlexW2602800732MaRDI QIDQ4360134

Neal E. Young, Samir Khuller, Balaji Raghavachari, Sándor P. Fekete, Monika Klemmstein

Publication date: 20 September 1998

Published in: Journal of Algorithms, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0205050

zbMATH Keywords

edge weightperformance guaranteepositive flowlow-weight spanning treeminimum span treespan tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10)

Related Items (15)

A 4-approximation of the \(\frac{2\pi }{3} \)-MST ⋮ Network design with edge-connectivity and degree constraints ⋮ Approximating bounded-degree spanning trees and connected factors with leaves ⋮ Approximation algorithms for connected graph factors of minimum weight ⋮ On improved bounds for bounded degree spanning trees for points in arbitrary dimension ⋮ Using Lagrangian dual information to generate degree constrained spanning trees ⋮ Cooperative TSP ⋮ Algorithms for the metric ring star problem with fixed edge-cost ratio ⋮ Resource allocation in bounded degree trees ⋮ Degree-bounded minimum spanning trees ⋮ Euclidean bottleneck bounded-degree spanning tree ratios ⋮ Degree-bounded minimum spanning tree for unit disk graph ⋮ Bounded-angle minimum spanning trees ⋮ A 4-approximation of the \(\frac{ 2 \pi}{ 3} \)-MST ⋮ Electrical flows over spanning trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge exchanges in the degree-constrained minimum spanning tree problem
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• Transitions in geometric minimum spanning trees
• Design of survivable networks
• Euclidean spanner graphs with degree four
• Low-degree minimum spanning trees
• Balancing minimum spanning trees and shortest-path trees
• Low degree spanning trees of small weight
• Efficient algorithms for a family of matroid intersection problems
• On two geometric problems related to the travelling salesman problem
• Topological design of centralized computer networks—formulations and algorithms
• A good algorithm for smallest spanning trees with a degree constraint
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Many birds with one stone

This page was built for publication: A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees