dc.contributor.author |
Arthanari, Tirukkattuppalli |
en |
dc.date.accessioned |
2012-03-15T19:59:51Z |
en |
dc.date.issued |
2006 |
en |
dc.identifier.citation |
Discrete Mathematics 306(14):1474-1492 2006 |
en |
dc.identifier.issn |
0012-365X |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/14456 |
en |
dc.description.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. |
en |
dc.description.uri |
http://www.sciencedirect.com/ |
en |
dc.publisher |
Elsevier |
en |
dc.relation.ispartofseries |
Discrete Mathematics |
en |
dc.rights |
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Details obtained from http://www.sherpa.ac.uk/romeo/issn/0012-365X/ |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.title |
On pedigree polytopes and Hamiltonian cycles |
en |
dc.type |
Journal Article |
en |
dc.identifier.doi |
10.1016/j.disc.2005.11.030 |
en |
pubs.begin-page |
1474 |
en |
pubs.volume |
306 |
en |
dc.rights.holder |
Copyright: Elsevier |
en |
pubs.end-page |
1492 |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/RestrictedAccess |
en |
pubs.subtype |
Article |
en |
pubs.elements-id |
71488 |
en |
pubs.org-id |
Business and Economics |
en |
pubs.org-id |
Info Systems & Operations Mgmt |
en |
pubs.record-created-at-source-date |
2010-09-01 |
en |