Matroidal degree-bounded minimum spanning trees

MaRDI QIDQ5743495zbMATH OpenFDO

Authors Rico Zenklusen

Publication date 10 May 2019

Full work available at URL https://arxiv.org/abs/1107.5329, https://dl.acm.org/citation.cfm?id=2095236

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

• A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
• Approximating minimum bounded degree spanning trees to within one of optimal
• Chain-constrained spanning trees

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
• Additive guarantees for degree-bounded directed network design
• Approximating minimum bounded degree spanning trees to within one of optimal
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Approximation algorithms for finding low-degree subgraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Degree Bounded Matroids and Submodular Flows
• scientific article; zbMATH DE number 5485590 (Why is no real title available?)
• Improved Approximation Algorithms for Uniform Connectivity Problems
• Multi-budgeted matchings and matroid intersection via dependent rounding
• Primal-dual meets local search: approximating MST's with nonuniform degree bounds
• Survivable network design with degree or order constraints
• What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs

Cited in

(15)

• Degree-bounded minimum spanning trees
• The vertex degrees of minimum spanning trees
• Chain-constrained spanning trees
• Refuting a conjecture of goemans on bounded degree spanning trees
• \(k\)-trails: recognition, complexity, and approximations
• The computational complexity of the k-minimum spanning tree problem in graded matrices
• Degree bounded matroids and submodular flows
• New approaches to multi-objective optimization
• Chain-constrained spanning trees
• Popular matchings with ties and matroid constraints
• Approximate multi-matroid intersection via iterative refinement
• Approximating maximum-size properly colored forests
• Approximating maximum-size properly colored forests
• Perfect hierarchical matchings in graphs
• Degree-bounded minimum spanning tree for unit disk graph

This page was built for publication: Matroidal degree-bounded minimum spanning trees

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