首页 | 本学科首页   官方微博 | 高级检索  
     检索      


The traveling salesman problem in graphs with some excluded minors
Authors:Jean Fonlupt  Denis Naddef
Institution:(1) Université J. Fourier, IMAG-Artemis, 38041 Grenoble, France
Abstract:Given a graph and a length function defined on its edge-set, the Traveling Salesman Problem can be described as the problem of finding a family of edges (an edge may be chosen several times) which forms a spanning Eulerian subgraph of minimum length. In this paper we characterize those graphs for which the convex hull of all solutions is given by the nonnegativity constraints and the classical cut constraints. This characterization is given in terms of excluded minors. A constructive characterization is also given which uses a small number of basic graphs.
Keywords:Graph  Eulerian graph  Hamilton cycle  polyhedron  Traveling Salesman Problem
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号