CCE Faculty Articles

Another greedy heuristic for the constrained forest problem

Document Type

Article

Publication Title

Operations Research Letters

ISSN

0167-6377

Publication Date

11-1-2005

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.

DOI

10.1016/j.orl.2004.11.010

Volume

33

Issue

6

First Page

629

Last Page

633

Link to Full Text

Find in your library

Share

COinS