Degree-bounded minimum spanning trees
From MaRDI portal
Publication:1028423
DOI10.1016/j.dam.2008.03.037zbMath1169.05315OpenAlexW2072970094MaRDI QIDQ1028423
Raja Jothi, Balaji Raghavachari
Publication date: 30 June 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.03.037
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (12)
A 4-approximation of the \(\frac{2\pi }{3} \)-MST ⋮ What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs ⋮ On the area requirements of Euclidean minimum spanning trees ⋮ Polynomial area bounds for MST embeddings of trees ⋮ An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem ⋮ Bounded-angle spanning tree: modeling networks with angular constraints ⋮ Algorithms for Euclidean Degree Bounded Spanning Tree Problems ⋮ Degree-bounded minimum spanning trees ⋮ Euclidean bottleneck bounded-degree spanning tree ratios ⋮ 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
Cites Work
- Unnamed Item
- Degree-bounded minimum spanning trees
- Transitions in geometric minimum spanning trees
- Euclidean spanner graphs with degree four
- Approximation schemes for NP-hard geometric optimization problems: a survey
- Euclidean bounded-degree spanning tree ratios
- Approximation schemes for degree-restricted MST and red-blue separation problems
- Low-degree minimum spanning trees
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- On two geometric problems related to the travelling salesman problem
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees
- Hamilton Paths in Grid Graphs
- Low-Degree Spanning Trees of Small Weight
- CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
- Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Approximation algorithms for degree-constrained minimum-cost network-design problems
This page was built for publication: Degree-bounded minimum spanning trees
