The Travelling Salesman Problem in Graphs with 3-Edge Cutsets.
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
In this paper the authors decomposition properties of a graph which, when they occur, permit a polynomial solution of the traveling salesmen problem and a description of the travelling salesman polytope by a system of linear equalities and inequalities. The central notion is that of a 3-edge cutset, namely a set of 3 edges which, when removed, disconnects the graph. Conversely, their approach can be used to construct classes of graphs for which there exists a polynomial algorithm for the travelling salesman problem. The approach on two examples is illustrated Halin graphs and prismatic graphs. Author
- Theoretical Mathematics