Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
From MaRDI portal
Publication:5317173
DOI10.1137/S0097539702418048zbMath1075.68101MaRDI QIDQ5317173
Publication date: 16 September 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Lagrangian relaxation; approximation algorithms; network algorithms; spanning trees; bicriteria approximation; degree-bounded spanning trees
90C35: Programming involving graphs or networks
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal, On generalizations of network design problems with degree bounds, Network design with weighted degree constraints, Budgeted matching and budgeted matroid intersection via the gasoline puzzle, Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree, Degree-bounded minimum spanning trees, The \((K, k)\)-capacitated spanning tree problem, An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem, A 2k-vertex Kernel for Maximum Internal Spanning Tree, Multi-objective Problems in Terms of Relational Algebra, Network Design with Weighted Degree Constraints
