| Article ID: | iaor2006944 |
| Country: | Netherlands |
| Volume: | 33 |
| Issue: | 6 |
| Start Page Number: | 629 |
| End Page Number: | 633 |
| Publication Date: | Nov 2005 |
| Journal: | Operations Research Letters |
| Authors: | Mukherjee Sumitra, Laszlo Michael |
| Keywords: | heuristics |
The constrained forest problem seeks a minimum-weight spanning forest in an undirected edge-weighted graph such that each tree spans at least a specified number of vertices. We present a greedy heuristic for this NP-hard problem, whose solutions are at least as good as, and often better than, those produced by the best-known 2-approximate heuristic.