New Insights on Prize Collecting Path Problems

  • Edcarllos Santos UFF
  • Alfredo Candia-Véjar Universidad de Talca
  • Luiz Satoru Ochi UFF
  • Luidi Simonetti UFRJ
  • Uéverton S. Souza UFF
DOI: https://doi.org/10.5753/etc.2017.3182

Resumo


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.

Referências

Itai, A., Papadimitriou, C. H., e Szwarcfiter, J. L. (1982). Hamilton Paths in Grid Graphs. SIAM Journal on Computing, 11(4):676–686. ISSN 0097-5397.

Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations, p. 85–103. Springer US, Boston, MA.
Publicado
02/07/2017
Como Citar

Selecione um Formato
SANTOS, Edcarllos; CANDIA-VÉJAR, Alfredo; OCHI, Luiz Satoru; SIMONETTI, Luidi; SOUZA, Uéverton S.. New Insights on Prize Collecting Path Problems. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . p. 21-24. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3182.