Approximating minimum bounded degree spanning trees to within one of optimal

DOI10.1145/1250790.1250887MaRDI QIDQ3549667zbMATH OpenOpenAlexFDO

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

(39)

• 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
• Fast combinatorial algorithms for efficient sortation
• \(k\)-trails: recognition, complexity, and approximations
• Fast combinatorial algorithms for efficient sortation
• Approximating Directed Weighted-Degree Constrained Networks
• Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
• Degree constrained node-connectivity problems
• \(k\)-trails: recognition, complexity, and approximations
• Fast approximation algorithm for maximum lifetime aggregation trees in wireless sensor networks
• Multiple facility location on a network with linear reliability order of edges
• Matroidal degree-bounded minimum spanning trees
• Spanning tree with lower bound on the degrees
• On improved bounds for bounded degree spanning trees for points in arbitrary dimension
• Approximating directed weighted-degree constrained networks
• An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
• Iterative packing for demand and hypergraph matching
• Chain-constrained spanning trees
• Degree bounded matroids and submodular flows
• 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)