Linked from

The 17 pages that link to Travelling salesman problem, each with the reason it gives.

• Complete graphRelated: Its standard graph model connects every city pair, often with weighted complete graphs.

• Shortest path problemCompared with: It requires a global visit-and-return tour rather than a route between two vertices.

• Computational complexity theoryBroader topic: Its optimization form exemplifies problems that are hard to solve exactly at scale.

• Integer programmingBroader topic: Integer variables select tour edges, while constraints eliminate disconnected subtours.

• NP-completenessBroader topic: Its decision version is NP-complete, connecting route planning to the class.

• Path (graph theory)Related: Its tours are closed routes closely related to Hamiltonian cycles and paths.

• Combinatorial optimizationBroader topic: It is a defining example of selecting an optimal permutation under a global cost.

• Assignment problemCompared with: It adds a single-tour connectivity requirement absent from ordinary assignment.

• NP-hardnessBroader topic: Its optimization form is NP-hard, while its decision form is NP-complete.

• Vehicle routing problemNarrower topic: A single-vehicle routing problem reduces to this tour problem when capacity and other constraints are absent.

• Linear programming relaxationBroader topic: LP relaxations of tour formulations expose fractional subtours and motivate cutting planes.

• Hamiltonian cycleRelated: Its tours are Hamiltonian cycles in weighted graphs, with cost added as an objective.

• Hamiltonian pathRelated: Its tours are Hamiltonian cycles with edge costs and an optimization objective.

• Hamiltonian path problemCompared with: It adds edge costs and a return requirement to a Hamiltonian-cycle-style search.

• Mathematical problemBroader topic: It exemplifies how a clear task can become computationally difficult as its instances grow.

• Gilbert–Pollak conjectureCompared with: Unlike Steiner trees, tours must visit terminals in a cycle and cannot exploit free junctions.

• Richard M. KarpBroader topic: Karp’s work helped establish this classic optimization problem’s NP-completeness.