The subdivision-constrained minimum spanning tree problem
The subdivision-constrained minimum spanning tree problem
复制标题
细分约束的最小生成树问题
DOI：
10.1016/j.tcs.2008.12.038
复制
发表时间：
2009-03
影响因子：
1.1
通讯作者：
Li, Jianping
中科院分区：
文献类型：
--
作者：
Li, Weidong;Zhang, Tongquan;Zhang, Zhongxu;Li, Jianping
受Hassin和Levin [R. Hassin，A. Levin，An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection，SIAM Journal on Computing 33（2）（2004）261-268]，本文研究了一个新的组合优化问题，称为一般细分约束生成树问题（GSCST）：给定图G=（V，E; w，c），其中对于每条边e∈E，有两个非负整数w（e）和c（e），两个正整数B和d，GSCST问题是首先找到G的具有权重的生成树T=（V，ET）[公式：然后在T中的一些合适的边上插入一些新的顶点，使得T的细分树T′中的每条边的权重不超过d。目标是使成本最小化[公式：在满足上述两个约束条件的情况下，在G的所有生成树中的合适的边上插入这样的新顶点，其中通过在T中的合适的边上插入一些新顶点来构造T的细分树T′，值insert（e）= dlw（e）d lw-1是插入的顶点的最少数量，c（e）是插入在边e上的每个顶点的成本。主要结果如下：（1）GSCST问题及其变形仍然是NP-难的，分别是0-1背包问题的一个约化：（2）GSCST问题及其变形与CST问题是多项式等价的，这意味着存在一个多项式时间的近似方案来求解GSCST问题及其变形;（3）设计了三个强多项式时间算法，分别求解GSCST问题的特殊形式及其变形。
Motivated by the constrained minimum spanning tree (CST) problem in Hassin and Levin [R. Hassin, A. Levin, An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection, SIAM Journal on Computing 33 (2) (2004) 261–268], we study a new combinatorial optimization problem in this paper, called the general subdivision-constrained spanning tree problem (GSCST): given a graph G=(V,E;w,c) with two nonnegative integers w(e) and c(e) for each edge e∈E, two positive integers B and d, the GSCST problem is to first find a spanning tree T=(V,ET) of G with weight [Formula: see text] and then to insert some new vertices on some suitable edges in T such that each edge in the subdivision tree T′of T has its weight not beyond d. The objective is to minimize the cost [Formula: see text] of such new vertices inserted on the suitable edges among all spanning trees of G subject to the two preceding constraints, where a subdivision tree T′of T is constructed by inserting some new vertices on the suitable edges in T, the value insert(e)=⌈w(e)d⌉−1 is the least number of vertices inserted and c(e) is the cost of each vertex inserted on the edge e. We obtain the following main results: (1) the GSCST problem and its variant are still NP-hard, by a reduction from the 0–1 knapsack problem, respectively; (2) the GSCST problem as well as its variant is polynomially equivalent to the CST problem, which implies the existence of a polynomial time approximation scheme to solve the GSCST problem and its variant; (3) we finally design three strongly polynomial time algorithms to solve the special versions of the GSCST problem and its variant, respectively.
登录
查看更多内容
影响因子：
3.7
作者：
C. Berge;A. Ghouila-Houri;M. Merrington;C. Ramanujacharyulu
通讯作者：
C. Berge;A. Ghouila-Houri;M. Merrington;C. Ramanujacharyulu
DOI：
10.1093/comjnl/9.2.166
发表时间：
1966-08
期刊：
The Computer Journal
影响因子：
--
作者：
K. Haley
通讯作者：
K. Haley
DOI：
10.1016/j.orl.2003.06.003
发表时间：
2004-05
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
Sung-Pil Hong;Sung-Jin Chung;B. Park
通讯作者：
Sung-Pil Hong;Sung-Jin Chung;B. Park
DOI：
10.1137/s0097539703426775
发表时间：
2004-02
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Refael Hassin;Asaf Levin
通讯作者：
Refael Hassin;Asaf Levin
DOI：
10.1057/jors.1977.45
发表时间：
1978-03
期刊：
--
影响因子：
--
作者：
E. Lloyd;J. Bondy;U. Murty
通讯作者：
E. Lloyd;J. Bondy;U. Murty