| Article ID: | iaor1996293 |
| Country: | Netherlands |
| Volume: | 56 |
| Issue: | 1 |
| Start Page Number: | 9 |
| End Page Number: | 18 |
| Publication Date: | Jan 1995 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Fischetti Matteo |
| Keywords: | graphs, programming: travelling salesman |
This paper solves, in the affermative, the open question of whether the Grötschel-Pulleyblank clique tree inequalities define facets of the asymmetric traveling salesman polytope and its monotonization. This generalizes the corresponding result for symmetric polytopes. The proof makes use of a new recursive definition of clique tree, based on induction on the number of its ‘teeth’ rather than of its ‘handles’.