Generalized spanning trees

M. Dror; M. Haouari; J. Chaouachi

doi:10.1016/S0377-2217(99)00006-5

Generalized spanning trees

M. Dror, M. Haouari, J. Chaouachi

Management Information Systems

Research output: Contribution to journal › Article › peer-review

49 Scopus citations

Abstract

In this paper, we propose a definition for the Generalized Minimal Spanning Tree (GMST) of a graph. The GMST requires spanning at least one node out of every set of disjoint nodes (node partition) in a graph. The analysis of the GMST problem is motivated by real life agricultural settings related to construction of irrigation networks in desert environments. We prove that the GMST problem is NP-hard, and examine a number of heuristic solutions for this problem. Computational experiments comparing these heuristics are presented.

Original language	English (US)
Pages (from-to)	583-592
Number of pages	10
Journal	European Journal of Operational Research
Volume	120
Issue number	3
DOIs	https://doi.org/10.1016/S0377-2217(99)00006-5
State	Published - Feb 1 2000

ASJC Scopus subject areas

General Computer Science
Modeling and Simulation
Management Science and Operations Research
Information Systems and Management

Access to Document

10.1016/S0377-2217(99)00006-5

Cite this

@article{eda0c7705a4f4c3ca3c075ad3dc6d28b,

title = "Generalized spanning trees",

abstract = "In this paper, we propose a definition for the Generalized Minimal Spanning Tree (GMST) of a graph. The GMST requires spanning at least one node out of every set of disjoint nodes (node partition) in a graph. The analysis of the GMST problem is motivated by real life agricultural settings related to construction of irrigation networks in desert environments. We prove that the GMST problem is NP-hard, and examine a number of heuristic solutions for this problem. Computational experiments comparing these heuristics are presented.",

author = "M. Dror and M. Haouari and J. Chaouachi",

note = "Funding Information: This work was supported in part by a grant from the International Development Research Centre (Canada). The second author would like to thank Professor Mohamed Salah Mattoussi for his constant support and several very insightful suggestions. ",

year = "2000",

month = feb,

day = "1",

doi = "10.1016/S0377-2217(99)00006-5",

language = "English (US)",

volume = "120",

pages = "583--592",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Generalized spanning trees

AU - Dror, M.

AU - Haouari, M.

AU - Chaouachi, J.

N1 - Funding Information: This work was supported in part by a grant from the International Development Research Centre (Canada). The second author would like to thank Professor Mohamed Salah Mattoussi for his constant support and several very insightful suggestions.

PY - 2000/2/1

Y1 - 2000/2/1

N2 - In this paper, we propose a definition for the Generalized Minimal Spanning Tree (GMST) of a graph. The GMST requires spanning at least one node out of every set of disjoint nodes (node partition) in a graph. The analysis of the GMST problem is motivated by real life agricultural settings related to construction of irrigation networks in desert environments. We prove that the GMST problem is NP-hard, and examine a number of heuristic solutions for this problem. Computational experiments comparing these heuristics are presented.

AB - In this paper, we propose a definition for the Generalized Minimal Spanning Tree (GMST) of a graph. The GMST requires spanning at least one node out of every set of disjoint nodes (node partition) in a graph. The analysis of the GMST problem is motivated by real life agricultural settings related to construction of irrigation networks in desert environments. We prove that the GMST problem is NP-hard, and examine a number of heuristic solutions for this problem. Computational experiments comparing these heuristics are presented.

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

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

U2 - 10.1016/S0377-2217(99)00006-5

DO - 10.1016/S0377-2217(99)00006-5

M3 - Article

AN - SCOPUS:0033908431

SN - 0377-2217

VL - 120

SP - 583

EP - 592

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 3

ER -

Generalized spanning trees

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this