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

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1983
Accession Number
ADA133504

Entities

People

  • D. Naddef
  • G. Cornuejols
  • W. Pulleyblank

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Blood Coagulation Factors
  • Coefficients
  • Computer Programming
  • Cost Reductions
  • Costs
  • Decomposition
  • Embedding
  • Engineering
  • Equations
  • Inequalities
  • Linear Programming
  • Linear Systems
  • Optimization
  • Polynomials
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research