Approximating minimum-cost graph problems with spanning tree edges

DOI10.1016/0167-6377(94)90067-1MaRDI QIDQ1892100zbMATH OpenOpenAlexFDO

Authors Michel X. Goemans, David P. Williamson

Publication date 6 July 1995

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(94)90067-1

zbMATH Keywords

location-routing problemsminimum-cost spanning tree2- matchingNP-hard minimum-cost graph problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• Approximating the degree-bounded minimum diameter spanning tree problem
• Approximating the degree-bounded minimum diameter spanning tree problem
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Approximating minimum bounded degree spanning trees to within one of optimal
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• scientific article; zbMATH DE number 1303537
• scientific article; zbMATH DE number 1305417
• scientific article; zbMATH DE number 1756011
• Approximating the Minimum Spanning Tree Weight in Sublinear Time

Cites work

• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 4051316 (Why is no real title available?)
• scientific article; zbMATH DE number 1263260 (Why is no real title available?)
• scientific article; zbMATH DE number 742977 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• A greedy heuristic for a minimum-weight forest problem
• A matching problem with side conditions
• A primal-dual approximation algorithm for generalized Steiner network problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• Geometric algorithms and combinatorial optimization
• Hamiltonian location problems

Cited in

(22)

• Approximation algorithms for minimum tree partition
• Edge exchanges in the degree-constrained minimum spanning tree problem
• Minimum cost spanning tree problems as value sharing problems
• A polynomial time approximation scheme for the two-source minimum routing cost spanning trees
• A constant-factor approximation for directed latency in quasi-polynomial time
• A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
• Upgrading min-max spanning tree problem under various cost functions
• On the set of extreme core allocations for minimal cost spanning tree problems
• A General Approximation Technique for Constrained Forest Problems
• Eulerian location problems
• Improving the approximation ratio for capacitated vehicle routing
• Approximation algorithms for constructing required subgraphs using stock pieces of fixed length
• Simple greedy algorithms for fundamental multidimensional graph problems
• Additivity in minimum cost spanning tree problems
• Minimum cost spanning tree problems with groups
• A 3/2-approximation algorithm for some minimum-cost graph problems
• Spanning Trees and Optimization Problems
• A survey of the standard location-routing problem
• An axiomatic approach in minimum cost spanning tree problems with groups
• Approximation Algorithms for a Network Design Problem
• scientific article; zbMATH DE number 447202 (Why is no real title available?)
• An approximation algorithm for network design problems with downwards-monotone demand functions

This page was built for publication: Approximating minimum-cost graph problems with spanning tree edges

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