On pedigree polytopes and Hamiltonian cycles |
| |
Authors: | TS Arthanari |
| |
Institution: | Department of ISOM, University of Auckland, 7, Symonds Street, Auckland, New Zealand |
| |
Abstract: | In this paper we define a combinatorial object called a pedigree, and study the corresponding polytope, called the pedigree polytope. Pedigrees are in one-to-one correspondence with the Hamiltonian cycles on Kn. Interestingly, the pedigree polytope seems to differ from the standard tour polytope, Qn with respect to the complexity of testing whether two given vertices of the polytope are nonadjacent. A polynomial time algorithm is given for nonadjacency testing in the pedigree polytope, whereas the corresponding problem is known to be NP-complete for Qn. We also discuss some properties of the pedigree polytope and illustrate with examples. |
| |
Keywords: | Hamiltonian cycles Symmetric Traveling Salesman Problem Pedigree polytope Nonadjacency testing Multistage insertion formulation Flows in networks |
本文献已被 ScienceDirect 等数据库收录! |
|