Advanced search
Start date

A computational study for the Prize-Collecting dominating cycle problem

Grant number: 16/05036-1
Support Opportunities:Scholarships in Brazil - Scientific Initiation
Effective date (Start): September 01, 2016
Effective date (End): February 28, 2017
Field of knowledge:Engineering - Production Engineering - Operational Research
Principal Investigator:Fábio Luiz Usberti
Grantee:Luis Henrique Pauleti Mendes
Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil


This research project proposes methodologies to solve the Prize Collecting Dominanting Cycle Problem (PCDCP). This problem is the composition of two NP-hard problems: the Dominating Set Problem and the Traveling Salesman Problem. Briefly, the aim of the PCDCP is to find a minimum cost cycle in an undirected graph. A traveler who needs to visit a set of customers (dominant vertices) traverses the cycle. The motivation of the PCDCP consists in its practical application to companies that deal with transportation, distribution and collection of products~ particularly, in the process of definition of the routes to carry out these services. In this research project, we will study methodologies to solve the PCDCP, considering the complexity of the exact solution of the PCDCP.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list by writing to: