Approximating minimum-cost graph problems with spanning tree edges
From MaRDI portal
Publication:1892100
DOI10.1016/0167-6377(94)90067-1zbMATH Open0823.90125OpenAlexW2047085423MaRDI QIDQ1892100FDOQ1892100
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
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
- Fibonacci heaps and their uses in improved network optimization algorithms
- Geometric algorithms and combinatorial optimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Hamiltonian location problems
- A matching problem with side conditions
- Title not available (Why is that?)
- A greedy heuristic for a minimum-weight forest problem
- Title not available (Why is that?)
- A primal-dual approximation algorithm for generalized Steiner network problems
Cited In (22)
- Title not available (Why is that?)
- A constant-factor approximation for directed latency in quasi-polynomial time
- A 3/2-approximation algorithm for some minimum-cost graph problems
- Approximation algorithms for minimum tree partition
- Additivity in minimum cost spanning tree problems
- A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
- A polynomial time approximation scheme for the two-source minimum routing cost spanning trees
- Minimum cost spanning tree problems with groups
- A survey of the standard location-routing problem
- Eulerian location problems
- Upgrading min-max spanning tree problem under various cost functions
- Improving the approximation ratio for capacitated vehicle routing
- An axiomatic approach in minimum cost spanning tree problems with groups
- Simple greedy algorithms for fundamental multidimensional graph problems
- An approximation algorithm for network design problems with downwards-monotone demand functions
- On the set of extreme core allocations for minimal cost spanning tree problems
- Approximation algorithms for constructing required subgraphs using stock pieces of fixed length
- Spanning Trees and Optimization Problems
- Approximation Algorithms for a Network Design Problem
- Edge exchanges in the degree-constrained minimum spanning tree problem
- Minimum cost spanning tree problems as value sharing problems
- A General Approximation Technique for Constrained Forest Problems
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)
