CEC Faculty Articles

Title

Another greedy heuristic for the constrained forest problem

Document Type

Article

Date

11-1-2005

Publication Title

Operations Research Letters

ISSN or ISBN

0167-6377

Volume

33

Issue

6

First Page

629

Last Page

633

Description

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.

DOI

10.1016/j.orl.2004.11.010