On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets |
| |
Authors: | Martin Grötschel Yoshiko Wakabayashi |
| |
Institution: | Institut für Ökonometrie und Operations Research Universität Bonn, W. Germany;Instituto de Matemática e Estatistica da Universidade de Sāo Paulo, Brasil |
| |
Abstract: | The monotone asymmetric travelling salesman polytope P?nT is defined to be the convex hull of the incidence vectors of all hamiltonian circuits and all subsets of these in a complete diagraph of order n. We prove that certain hypohamiltonian diagraphs G=(V,E), i.e. diagraphs which are not hamiltonian but such that G–υ is hamiltonian for all υ?V, induce facets x(E)?n–1 of P?nT. This result indicates that P?nT has very complicated facets and that it is very unlikely that an explicit complete characterization of P?nT can ever be given. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |