A greedy heuristic for a minimum-weight forest problem

DOI10.1016/0167-6377(93)90097-ZzbMath0804.90124MaRDI QIDQ1317004

Leonid G. Khachiyan, Bahman Kalantari, Celina Imielinska

Publication date: 24 March 1994

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

zbMATH Keywords

polynomial algorithmminimum spanning treegreedy heuristicminimum weight collection of edgesminimum-weight forest problem

Mathematics Subject Classification ID

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

Related Items (13)

md-MST is NP-hard for ⋮ Approximating minimum-cost graph problems with spanning tree edges ⋮ Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations ⋮ Approximation Algorithms for a Network Design Problem ⋮ On the complexity of graph tree partition problems. ⋮ An approximation algorithm for network design problems with downwards-monotone demand functions ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ Heuristic approaches for the optimal wiring in large scale robotic skin design ⋮ Complexity and approximation of the constrained forest problem ⋮ Approximation algorithms for minimum tree partition ⋮ A 3/2-approximation algorithm for some minimum-cost graph problems ⋮ A class of heuristics for the constrained forest problem ⋮ Another greedy heuristic for the constrained forest problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A matching problem with side conditions
• A general class of heuristics for minimum weight perfect matching and fast special cases with doubly and triply logarithmic errors
• Heuristic matching for graphs satisfying the triangle inequality
• A new class of heuristic algorithms for weighted perfect matching
• Paths, Trees, and Flowers

This page was built for publication: A greedy heuristic for a minimum-weight forest problem