Accession Number:

ADA133504

Title:

The Travelling Salesman Problem in Graphs with 3-Edge Cutsets.

Descriptive Note:

Research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1983-08-01

Pagination or Media Count:

52.0

Abstract:

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE