What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs

DOI10.1007/S00453-007-9115-5MaRDI QIDQ2391179zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 24 July 2009

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9115-5

zbMATH Keywords

combinatorial optimizationmatchingapproximation algorithmsminimum spanning trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
• Primal-dual meets local search: approximating MST's with nonuniform degree bounds
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids

Cites work

• scientific article; zbMATH DE number 2081108 (Why is no real title available?)
• A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
• A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• 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, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Degree-bounded minimum spanning trees
• Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
• Euclidean bounded-degree spanning tree ratios
• Low-Degree Spanning Trees of Small Weight
• Many birds with one stone
• Maximum matching and a polyhedron with 0,1-vertices
• Network Flow and Testing Graph Connectivity
• On two geometric problems related to the travelling salesman problem
• Paths, Trees, and Flowers
• Primal-dual meets local search: approximating MST's with nonuniform degree bounds
• Topological design of centralized computer networks—formulations and algorithms
• Toughness, trees, and walks

Cited in

(14)

• Bounded-degree light approximate shortest-path trees in doubling metrics
• Refuting a conjecture of goemans on bounded degree spanning trees
• The maximum binary tree problem
• Network design with weighted degree constraints
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• The Maximum Binary Tree Problem.
• Approximating minimum bounded degree spanning trees to within one of optimal
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• Primal-dual meets local search: approximating MST's with nonuniform degree bounds
• Matroidal degree-bounded minimum spanning trees
• A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
• Chain-constrained spanning trees
• A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids

This page was built for publication: What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs

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