Approximating minimum-cost graph problems with spanning tree edges
type: Item
instance of: scholarly article
title: Approximating minimum-cost graph problems with spanning tree edges
zbMATH Open document ID: 0823.90125
DOI: 10.1016/0167-6377(94)90067-1
author: Michel X. Goemans
author: David P. Williamson
published in: Operations Research Letters
publication date: 1995-07-06T00:00:00Z
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 761908
zbMATH Keywords: NP-hard minimum-cost graph problems
zbMATH Keywords: minimum-cost spanning tree
zbMATH Keywords: 2- matching
zbMATH Keywords: location-routing problems
MaRDI profile type: Publication
full work available at URL: 0167-6377(94)90067-1
OpenAlex ID: W2047085423
cites work: A matching problem with side conditions
cites work: Q5675543
cites work: Fibonacci heaps and their uses in improved network optimization algorithms
cites work: Q4234132
cites work: Q4763416
cites work: Geometric algorithms and combinatorial optimization
cites work: A greedy heuristic for a minimum-weight forest problem
cites work: Q3787762
cites work: Hamiltonian location problems
cites work: Q3694703
cites work: A primal-dual approximation algorithm for generalized Steiner network problems
Recommended article: Approximating the degree-bounded minimum diameter spanning tree problem
Recommended article: Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
Recommended article: A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
Recommended article: Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
Recommended article: A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
Recommended article: Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
Recommended article: Q4250159
Recommended article: Q4252299
Recommended article: Q4535797
Recommended article: Approximating the Minimum Spanning Tree Weight in Sublinear Time
description: scientific article; zbMATH DE number 761908