TY - JOUR
AU - Santos, Edcarllos
AU - Candia-Véjar, Alfredo
AU - Ochi, Luiz Satoru
AU - Simonetti, Luidi
AU - Souza, Uéverton S.
PY - 2017/07/02
TI - New Insights on Prize Collecting Path Problems
JF - Anais do Encontro de Teoria da Computação (ETC); 2017: Anais do II Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2017.3182
KW -
N2 - Given a graph G and a pair s,t in V(G), where each edge e has a weight t(e) and each vertex v has a value p(v) such that t(e) represent a transportation time and p(v) a prize collecting. Prize Collecting Path (PCP) consists of finding a (s,t)-path that minimizes the total transportation time minus the total prize of nodes in such path. PCP is at core of numerous relevant applications in several fields like telecommunications, transportation and logistics. In this paper, the complexity behavior of the problem is analyzed. For some cases we prove that PCP is NP-complete, these results lead to the generation of new sets of benchmark instances that are computationally hard according to natural characteristics of the problem. In addition, polynomial time algorithms are described for other cases and a mathematical formulation is introduced to solve general instances of PCP.
UR - https://sol.sbc.org.br/index.php/etc/article/view/3182