Supported in part by the National Natural Science Foundation of China under Grant No.11021161 and 10928102;973 Program of China under Grant No.2011CB80800;Chinese Academy of Sciences under Grant No.kjcx-yw-s7,project grant of"Center for Research and Applications in Plasma Physics and Pulsed Power Technology,PBCT-Chile-ACT 26";Direccio'n de Programas de Investigaci'ón,Universidad de Talca,Chile
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′V,the Prize Collecting Steiner Tree(PCST)problem is to find a tree T in G interc...