Approximating minimum bounded degree spanning trees to within one of optimal

DOI10.1145/1250790.1250887zbMATH Open1232.68184OpenAlexW2157421865MaRDI QIDQ3549667FDOQ3549667

Authors: Mohit Singh, Lap Chi Lau 

Publication date: 5 January 2009

Published in: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (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

iterative rounding methodminimum bounded degree spanning tree problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Cited In (37)

• Bounded-degree minimum-radius spanning trees in wireless sensor networks
• A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
• New approaches to multi-objective optimization
• Sharp separation and applications to exact and parameterized algorithms
• Network-design with degree constraints
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• Approximating Scheduling Machines with Capacity Constraints
• Network design with edge-connectivity and degree constraints
• Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands
• Refuting a conjecture of goemans on bounded degree spanning trees
• On some network design problems with degree constraints
• Network design with weighted degree constraints
• Improved approximation algorithms for maximum lifetime problems in wireless networks
• Network Design with Weighted Degree Constraints
• ILP formulation of the degree-constrained minimum spanning hierarchy problem
• A unified algorithm for degree bounded survivable network design
• The \((K, k)\)-capacitated spanning tree problem
• A computational study on the maximum-weight bounded-degree rooted tree problem
• What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
• Multi-objective Problems in Terms of Relational Algebra
• \(k\)-trails: recognition, complexity, and approximations
• Approximating Directed Weighted-Degree Constrained Networks
• Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
• Matroidal degree-bounded minimum spanning trees
• Degree constrained node-connectivity problems
• Fast approximation algorithm for maximum lifetime aggregation trees in wireless sensor networks
• \(k\)-trails: recognition, complexity, and approximations
• Multiple facility location on a network with linear reliability order of edges
• Spanning tree with lower bound on the degrees
• On improved bounds for bounded degree spanning trees for points in arbitrary dimension
• An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
• Iterative packing for demand and hypergraph matching
• Approximating directed weighted-degree constrained networks
• Degree bounded matroids and submodular flows
• Chain-constrained spanning trees
• A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem
• Multicommodity flow in trees: packing via covering and iterated relaxation

This page was built for publication: Approximating minimum bounded degree spanning trees to within one of optimal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549667)