کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949525 | 1440193 | 2017 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the longest path of a randomly weighted tournament
ترجمه فارسی عنوان
در طولانی ترین مسیر مسابقات با وزن تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مسابقات، توزیع تصادفی، طولانی ترین مسیر،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
If D has finite mean μ, then â(G,D)â¥Î¼(nâ1) is a trivial lower bound, with equality if D is constant, as by Redei's Theorem, every tournament has a Hamilton path. However, already for very simple nontrivial distributions, it is challenging to determine â(G,D) even asymptotically, and even if the tournament is small and fixed. We consider the two natural distributions of the random weighted model, the continuous uniform distribution U[0,1] and the symmetric Bernoulli distribution U{0,1}. Our first result is that for any tournament, both â(G,U{0,1}) and â(G,U[0,1]) are larger than the above trivial 0.5(nâ1) lower bound in the sense that 0.5 can be replaced by a larger constant. To this end we prove the existence of dense partial squares of Hamilton paths in any tournament, a combinatorial result which seems of independent interest. Regarding upper bounds, while for some tournaments one can prove that both â(G,U{0,1}) and â(G,U[0,1]) are nâo(n), we prove that there are other tournaments for which both â(G,U{0,1}) and â(G,U[0,1]) are significantly smaller. In particular, for every n, there are n-vertex tournaments for which â(G,U{0,1})â¤0.614(nâ1). Finally, we state several natural open problems arising in this setting.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 230, 30 October 2017, Pages 121-132
Journal: Discrete Applied Mathematics - Volume 230, 30 October 2017, Pages 121-132
نویسندگان
Raphael Yuster,