Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data

	Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data
	AlvarezMiranda Eduardo 2; CandiaVejar Alfredo 2; Chen Xujin 1; Hu Xiaodong 1; Li Bi 1
刊名	ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES
	2014
卷号	30 期号:1 页码:1-26
关键词	SERIES-PARALLEL GRAPHS SHORTEST-PATH PROBLEM COMPUTATIONAL-COMPLEXITY NETWORK OPTIMIZATION CONSTRAINTS ALGORITHMS FLOWS uncertainty modeling prize collecting Steiner tree interval data series-parallel graphs polynomial-time solvability
ISSN号	0168-9673
其他题名	Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data
英文摘要	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 subset of V, the Prize Collecting Steiner Tree (POST) 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 NP-hard in general, it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.
资助项目	[National Natural Science Foundation of China] ; [973 Program of China] ; [Chinese Academy of Sciences] ; [Center for Research and Applications in Plasma Physics and Pulsed Power Technology, PBCT-Chile-ACT 26] ; [Direccion de Programas de Investigacion, Universidad de Talca, Chile]
语种	英语
CSCD记录号	CSCD:5097895
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/53486]
专题	中国科学院数学与系统科学研究院
作者单位	1.中国科学院数学与系统科学研究院 2.University Talca, Ind Management Dept, Talca, Chile 3.University Bologna, DEI, I-40126 Bologna, Italy
推荐引用方式 GB/T 7714	AlvarezMiranda Eduardo,CandiaVejar Alfredo,Chen Xujin,et al. Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data[J]. ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES,2014,30(1):1-26.
APA	AlvarezMiranda Eduardo,CandiaVejar Alfredo,Chen Xujin,Hu Xiaodong,&Li Bi.(2014).Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data.ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES,30(1),1-26.
MLA	AlvarezMiranda Eduardo,et al."Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data".ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES 30.1(2014):1-26.