摘要
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