Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete

DOI10.1016/j.dam.2009.03.003zbMath1185.90168OpenAlexW2036433802MaRDI QIDQ967292

Gerardo Berbeglia, Geňa Hahn

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

zbMATH Keywords

complexitycounting solutions\#\(P\)-completetraveling salesman problem with pickups and deliveries

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

On the Complexity of Query Result Diversification ⋮ The counting complexity of a simple scheduling problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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