Article ID Journal Published Year Pages File Type
419707 Discrete Applied Mathematics 2009 7 Pages PDF
Abstract

Deciding whether or not a feasible solution to the Traveling Salesman Problem with Pickups and Deliveries   (TSPPD) exists is polynomially solvable. We prove that counting the number of feasible solutions of the TSPPD is hard by showing that the problem is #P#P-complete.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Counting feasible solutions of the traveling salesman problem with pickups and deliveries is #P#P-complete
Authors
, ,