Examples of some Intractable ProblemsPrevious:10.3
Examples of some Intractable Problems
10.3.1 Traveling Salesman Problem
A Hamiltonian cycle in an undirected graph is a simple cycle that passes
through every vertex exactly once.
Optimization Problem: Given a complete, weighted graph, find a minimum-weight
Decision Problem: Given a complete, weighted graph and an integer k,
does there exist a Hamiltonian cycle with total weight at most k.