A greedy heuristic for a minimum-weight forest problem

Celina Imielińska, Bahman Kalantari, Leonid Khachiyan

Research output: Contribution to journalArticle

23 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)65-71
Number of pages7
JournalOperations Research Letters
Volume14
Issue number2
DOIs
StatePublished - Jan 1 1993

Fingerprint

Greedy Heuristics
Approximate Solution
Spanning Forest
Triangle inequality
Minimum Spanning Tree
Weighted Graph
Natural number
Linear Time
Disjoint
Covering
NP-complete problem
Cycle
Graph in graph theory
Vertex of a graph
Heuristics
Graph

All Science Journal Classification (ASJC) codes

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

Cite this

Imielińska, Celina ; Kalantari, Bahman ; Khachiyan, Leonid. / A greedy heuristic for a minimum-weight forest problem. In: Operations Research Letters. 1993 ; Vol. 14, No. 2. pp. 65-71.
@article{e490f426f8ac48408afa93ffaeddb556,
title = "A greedy heuristic for a minimum-weight forest problem",
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.",
author = "Celina Imielińska and Bahman Kalantari and Leonid Khachiyan",
year = "1993",
month = "1",
day = "1",
doi = "10.1016/0167-6377(93)90097-Z",
language = "English (US)",
volume = "14",
pages = "65--71",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "2",

}

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

In: Operations Research Letters, Vol. 14, No. 2, 01.01.1993, p. 65-71.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Imielińska, Celina

AU - Kalantari, Bahman

AU - Khachiyan, Leonid

PY - 1993/1/1

Y1 - 1993/1/1

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.

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

VL - 14

SP - 65

EP - 71

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 2

ER -