Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10523997 | Operations Research Letters | 2005 | 5 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michael Laszlo, Sumitra Mukherjee,