Low-Degree Spanning Trees of Small Weight

DOI10.1137/S0097539794264585zbMath0849.05022OpenAlexW3099328339MaRDI QIDQ4877523

Neal E. Young, Samir Khuller, Balaji Raghavachari

Publication date: 3 November 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794264585

zbMATH Keywords

spanning treeNP-hardweight

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (16)

A 4-approximation of the \(\frac{2\pi }{3} \)-MST ⋮ What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs ⋮ Bounded-angle spanning tree: modeling networks with angular constraints ⋮ Binary Steiner trees: structural results and an exact solution approach ⋮ Using Lagrangian dual information to generate degree constrained spanning trees ⋮ Cooperative TSP ⋮ Algorithms for Euclidean Degree Bounded Spanning Tree Problems ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ The complexity of symmetric connectivity in directional wireless sensor networks ⋮ VNS and second order heuristics for the min-degree constrained minimum spanning tree problem ⋮ 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 push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids ⋮ A 4-approximation of the \(\frac{ 2 \pi}{ 3} \)-MST

This page was built for publication: Low-Degree Spanning Trees of Small Weight