### Abstract

Given an undirected edge-weighted graph and a natural number m, we consider the problem of finding a minimum-weight spanning forest such that each of its trees spans at least m vertices. For m ≥ 4, the problem is shown to the NP-hard. We describe a simple 2-approximate greedy heuristic that runs within the time needed to compute a minimum spanning tree. If the edge weights satisfy the triangle inequality, any such a 2-approximate solution, in linear time, can be converted into a 4-approximate solution for the problem of covering the graph with minimum-weight vertex disjoint cycles of size at least m.

Original language | English (US) |
---|---|

Pages (from-to) | 65-71 |

Number of pages | 7 |

Journal | Operations Research Letters |

Volume | 14 |

Issue number | 2 |

DOIs | |

State | Published - Sep 1993 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Software
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics

### Keywords

- approximate algorithms
- combinatorial problems

### Cite this

*Operations Research Letters*,

*14*(2), 65-71. https://doi.org/10.1016/0167-6377(93)90097-Z

}

*Operations Research Letters*, vol. 14, no. 2, pp. 65-71. https://doi.org/10.1016/0167-6377(93)90097-Z

**A greedy heuristic for a minimum-weight forest problem.** / Imielińska, Celina; Kalantari, Bahman; Khachiyan, Leonid.

Research output: Contribution to journal › Article

TY - JOUR

T1 - A greedy heuristic for a minimum-weight forest problem

AU - Imielińska, Celina

AU - Kalantari, Bahman

AU - Khachiyan, Leonid

PY - 1993/9

Y1 - 1993/9

N2 - Given an undirected edge-weighted graph and a natural number m, we consider the problem of finding a minimum-weight spanning forest such that each of its trees spans at least m vertices. For m ≥ 4, the problem is shown to the NP-hard. We describe a simple 2-approximate greedy heuristic that runs within the time needed to compute a minimum spanning tree. If the edge weights satisfy the triangle inequality, any such a 2-approximate solution, in linear time, can be converted into a 4-approximate solution for the problem of covering the graph with minimum-weight vertex disjoint cycles of size at least m.

AB - Given an undirected edge-weighted graph and a natural number m, we consider the problem of finding a minimum-weight spanning forest such that each of its trees spans at least m vertices. For m ≥ 4, the problem is shown to the NP-hard. We describe a simple 2-approximate greedy heuristic that runs within the time needed to compute a minimum spanning tree. If the edge weights satisfy the triangle inequality, any such a 2-approximate solution, in linear time, can be converted into a 4-approximate solution for the problem of covering the graph with minimum-weight vertex disjoint cycles of size at least m.

KW - approximate algorithms

KW - combinatorial problems

UR - http://www.scopus.com/inward/record.url?scp=38249004039&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249004039&partnerID=8YFLogxK

U2 - 10.1016/0167-6377(93)90097-Z

DO - 10.1016/0167-6377(93)90097-Z

M3 - Article

AN - SCOPUS:38249004039

VL - 14

SP - 65

EP - 71

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 2

ER -