Degree-bounded minimum spanning trees
From MaRDI portal
Publication:1028423
DOI10.1016/j.dam.2008.03.037zbMath1169.05315MaRDI 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
MST; approximation algorithm; network design; geometric optimization; minimum spanning trees; spanning trees
68Q25: Analysis of algorithms and problem complexity
05C05: Trees
05C35: Extremal problems in graph theory
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
On the area requirements of Euclidean minimum spanning trees, Polynomial area bounds for MST embeddings of trees, Degree-bounded minimum spanning trees, A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids, What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs, An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
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
