کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649185 | 1342445 | 2009 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An update on the middle levels problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An update on the middle levels problem An update on the middle levels problem](/preview/png/4649185.png)
چکیده انگلیسی
The middle levels problem is to find a Hamilton cycle in the middle levels, M2k+1, of the Hasse diagram of B2k+1 (the partially-ordered set of subsets of a 2k+1-element set ordered by inclusion). Previously, the best known, from [I. Shields, C.D. Savage, A Hamilton path heuristic with applications to the middle two levels problem, in: Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), vol. 140, 1999], was that M2k+1 is Hamiltonian for all positive k through k=15. In this note we announce that M33 and M35 have Hamilton cycles. The result was achieved by an algorithmic improvement that made it possible to find a Hamilton path in a reduced graph (of complementary necklace pairs) having 129,644,790 vertices, using a 64-bit personal computer.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 17, 6 September 2009, Pages 5271-5277
Journal: Discrete Mathematics - Volume 309, Issue 17, 6 September 2009, Pages 5271-5277
نویسندگان
Ian Shields, Brendan J. Shields, Carla D. Savage,