Approximating minimum bounded degree spanning trees to within one of optimal
From MaRDI portal
Publication:3549667
DOI10.1145/1250790.1250887zbMath1232.68184OpenAlexW2157421865MaRDI QIDQ3549667
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
Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (40)
ILP formulation of the degree-constrained minimum spanning hierarchy problem ⋮ Network design with edge-connectivity and degree constraints ⋮ k-Trails: Recognition, Complexity, and Approximations ⋮ Approximation-Friendly Discrepancy Rounding ⋮ What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs ⋮ On some network design problems with degree constraints ⋮ Approximating Scheduling Machines with Capacity Constraints ⋮ On generalizations of network design problems with degree bounds ⋮ The \((K, k)\)-capacitated spanning tree problem ⋮ Multiple facility location on a network with linear reliability order of edges ⋮ Bounded-degree minimum-radius spanning trees in wireless sensor networks ⋮ Multi-objective Problems in Terms of Relational Algebra ⋮ New approaches to multi-objective optimization ⋮ A unified algorithm for degree bounded survivable network design ⋮ Approximating directed weighted-degree constrained networks ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Network design with weighted degree constraints ⋮ Chain-constrained spanning trees ⋮ Refuting a conjecture of goemans on bounded degree spanning trees ⋮ Degree bounded matroids and submodular flows ⋮ A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem ⋮ Approximating Directed Weighted-Degree Constrained Networks ⋮ Degree constrained node-connectivity problems ⋮ Iterative Packing for Demand and Hypergraph Matching ⋮ Spanning tree with lower bound on the degrees ⋮ Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands ⋮ A computational study on the maximum-weight bounded-degree rooted tree problem ⋮ On improved bounds for bounded degree spanning trees for points in arbitrary dimension ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Budgeted matching and budgeted matroid intersection via the gasoline puzzle ⋮ Improved approximation algorithms for maximum lifetime problems in wireless networks ⋮ Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees ⋮ Network Design with Weighted Degree Constraints ⋮ Approximating MIN-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems ⋮ \(k\)-trails: recognition, complexity, and approximations ⋮ Network-Design with Degree Constraints ⋮ Fast Approximation Algorithm for Maximum Lifetime Aggregation Trees in Wireless Sensor Networks ⋮ A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids ⋮ Unnamed Item ⋮ An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
This page was built for publication: Approximating minimum bounded degree spanning trees to within one of optimal
