کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651442 | 1342546 | 2006 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On pedigree polytopes and Hamiltonian cycles
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On pedigree polytopes and Hamiltonian cycles On pedigree polytopes and Hamiltonian cycles](/preview/png/4651442.png)
چکیده انگلیسی
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 KnKn. Interestingly, the pedigree polytope seems to differ from the standard tour polytope, QnQn 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 QnQn. We also discuss some properties of the pedigree polytope and illustrate with examples.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issue 14, 28 July 2006, Pages 1474–1492
Journal: Discrete Mathematics - Volume 306, Issue 14, 28 July 2006, Pages 1474–1492
نویسندگان
T.S. Arthanari,