Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal

DOI10.1145/2629366zbMath1321.68507OpenAlexW2004163233MaRDI QIDQ5501947

Mohit Singh, Lap Chi Lau

Publication date: 14 August 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.433.674

zbMATH Keywords

approximation algorithmsspanning treesbounded degreeiterative rounding

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (22)

The generalized dependency constrained spanning tree problem ⋮ On approximating degree-bounded network design problems ⋮ Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Quasi-Popular Matchings, Optimality, and Extended Formulations ⋮ Exact Algorithms for the Minimum Load Spanning Tree Problem ⋮ A Spectral Approach to Network Design ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Reconfiguration of spanning trees with degree constraints or diameter constraints ⋮ Towards tight(er) bounds for the excluded grid theorem ⋮ Approximating bounded-degree spanning trees and connected factors with leaves ⋮ The Maximum Binary Tree Problem. ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ Approximation algorithms for connected graph factors of minimum weight ⋮ On approximating degree-bounded network design problems ⋮ The maximum binary tree problem ⋮ A unifying model for locally constrained spanning tree problems ⋮ Approximate multi-matroid intersection via iterative refinement ⋮ Thin trees in some families of distance-regular graphs ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Socially fair network design via iterative rounding ⋮ Electrical flows over spanning trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Network design via iterative rounding of setpair relaxations
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
• Testing membership in matroid polyhedra
• On a connection between the existence of k-trees and the toughness of a graph
• The ellipsoid method and its consequences in combinatorial optimization
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Iterative Methods in Combinatorial Optimization
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• Survivable Network Design with Degree or Order Constraints
• Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
• The traveling salesman problem on a graph and some related integer polyhedra
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Many birds with one stone
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• Matroids and the greedy algorithm

This page was built for publication: Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal