Another greedy heuristic for the constrained forest problem |
| |
| Authors: | Michael Laszlo Sumitra Mukherjee |
| |
| Institution: | Graduate School of Computer and Information Sciences, Nova Southeastern University, 3301 College Avenue, Ft. Lauderdale, FL 33314, USA |
| |
| 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: | Constrained forest problem Tree partitioning Minimum spanning forests Greedy heuristics |
| 本文献已被 ScienceDirect 等数据库收录！ |
