
Accession Number : ADA133504
Title : The Travelling Salesman Problem in Graphs with 3Edge Cutsets.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIEMELLON 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 3edge 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