Name
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. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1016/S0377-2217(99)00006-5 | European Journal of Operational Research |
Keywords | Field | DocType |
Agriculture,Irrigation network,Minimum spanning tree,Traveling salesman problem,Steiner problem,Worst case analysis,Genetic algorithms | Mathematical optimization,Combinatorics,Distributed minimum spanning tree,Steiner tree problem,Euclidean minimum spanning tree,Connected dominating set,Spanning tree,Shortest-path tree,Mathematics,Reverse-delete algorithm,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
120 | 3 | 0377-2217 |
Citations | PageRank | References |
19 | 1.60 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Moshe Dror | 1 | 574 | 64.77 |
| Mohamed Haouari | 2 | 706 | 55.24 |
| Jouhaina Chaouachi Siala | 3 | 53 | 5.62 |