期刊文献+

2014年第30卷第1期摘要(英文)

ACTA MATHEMATICAE APPLICATAE SINICA(English Series)
原文传递
导出
摘要 Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data——Xiao-dong HU,Bi LI Given a connected graph G=(V,E)with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V^1(?)V,the Prize Collecting Steiner Tree(PCST)problem is to find a tree T in G interconnecting all vertices of V_1 such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NPhard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs. Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data Xiao-dong HU, Bi LI Given a connected graph G = (V, E) with a nonnegative cost on each edge in E, a nonnegative prize at each vertex in V, and a target set V/ C V, the Prize Collecting Steiner Tree (PCST) problem is to find a tree T in G interconnecting all vertices of V' such that the total cost on edges in T minus the total prize at vertices in T is minimized. The PCST problem appears frequently in practice of operations research. While the problem is NP- hard in general, it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.
出处 《应用数学学报》 CSCD 北大核心 2014年第3期I0001-I0005,共5页 Acta Mathematicae Applicatae Sinica
  • 相关文献

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部