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) : Cornuejols,G ; Naddef,D ; Pulleyblank,W

PDF Url : ADA133504

Report Date : Aug 1983

Pagination or Media Count : 52

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)

Descriptors :   *Graphs, *Problem solving, Decomposition, Polynomials, Algorithms, Linearity, Inequalities, Reduction, Optimization, Linear programming, Edges, Set theory

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE