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

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

Sándor P. Fekete, Samir Khuller, Neal E. Young, Balaji Raghavachari, 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 weight; performance guarantee; positive flow; low-weight spanning tree; minimum span tree; span tree

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68R10: Graph theory (including graph drawing) in computer science

90C27: Combinatorial optimization

68W10: Parallel algorithms in computer science

Related Items

Using Lagrangian dual information to generate degree constrained spanning trees