Generalized spanning trees
Generalized spanning trees
复制标题
DOI：
10.1016/s0377-2217(99)00006-5
复制
发表时间：
2000-02-01
影响因子：
6.4
通讯作者：
Chaouachi, J
中科院分区：
文献类型：
--
作者：
Dror, M;Haouari, M;Chaouachi, J
在这篇论文中。提出了图的广义最小生成树的定义。GMST要求在图中的每个不相交节点集合（节点划分）中至少生成一个节点。GMST问题的分析是由真实的生活中的农业设置有关的灌溉网络在沙漠环境中的建设。我们证明了GMST问题是NP-难的，并研究了一些启发式解决方案，这个问题。计算实验比较这些proxistics。(C)2000 Elsevier Science B. V.保留所有权利。
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. (C) 2000 Elsevier Science B.V. All rights reserved.