Abstract
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) traver…