Degree-bounded minimum spanning trees
type: Item
instance of: scholarly article
title: Degree-bounded minimum spanning trees
zbMATH Open document ID: 1169.05315
author: Raja Jothi
author: Balaji Raghavachari
published in: Discrete Applied Mathematics
publication date: 2009-06-30T00:00:00Z
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5572522
zbMATH Keywords: spanning trees
zbMATH Keywords: minimum spanning trees
zbMATH Keywords: MST
zbMATH Keywords: approximation algorithm
zbMATH Keywords: geometric optimization
zbMATH Keywords: network design
MaRDI profile type: Publication
full work available at URL: j.dam.2008.03.037
OpenAlex ID: W2072970094
cites work: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
cites work: Approximation schemes for NP-hard geometric optimization problems: a survey
cites work: Approximation schemes for degree-restricted MST and red-blue separation problems
cites work: Euclidean bounded-degree spanning tree ratios
cites work: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
cites work: CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
cites work: A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees
cites work: Approximating the Minimum-Degree Steiner Tree to within One of Optimal
cites work: Q4198056
cites work: Hamilton Paths in Grid Graphs
cites work: Low-Degree Spanning Trees of Small Weight
cites work: A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
cites work: Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
cites work: Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
cites work: Transitions in geometric minimum spanning trees
cites work: On two geometric problems related to the travelling salesman problem
cites work: Approximation algorithms for degree-constrained minimum-cost network-design problems
cites work: Low-degree minimum spanning trees
cites work: Euclidean spanner graphs with degree four
DOI: 10.1016/J.DAM.2008.03.037
Recommended article: Minimum bottleneck spanning trees with degree bounds
Recommended article: Q5743495
Recommended article: Degree bounded spanning trees
Recommended article: Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
Recommended article: Spanning trees with bounded degrees
Recommended article: Spanning trees of bounded degree
Recommended article: Low-degree minimum spanning trees
Recommended article: Tree spanners of bounded degree graphs
Recommended article: Q4017161
Recommended article: Approximating the degree-bounded minimum diameter spanning tree problem
description: scientific article; zbMATH DE number 5572522