Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete
From MaRDI portal
Publication:967292
DOI10.1016/j.dam.2009.03.003zbMath1185.90168MaRDI QIDQ967292
Publication date: 28 April 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2009.03.003
complexity; counting solutions; \#\(P\)-complete; traveling salesman problem with pickups and deliveries
90C60: Abstract computational complexity for mathematical programming problems
90C27: Combinatorial optimization
Related Items
The counting complexity of a simple scheduling problem, On the Complexity of Query Result Diversification
Cites Work
- The complexity of computing the permanent
- The travelling salesman problem with pick-up and delivery
- The pickup and delivery problem: Faces and branch-and-cut algorithm
- Heuristics for the black and white traveling salesman problem
- Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs
- A constraint programming approach to the Chinese postman problem with time windows
- The Complexity of Enumeration and Reliability Problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item