اخبار و اعلانات

 آمار

تعداد نشریات43
تعداد شماره‌ها1,829
تعداد مقالات14,864
تعداد مشاهده مقاله40,707,998
تعداد دریافت فایل اصل مقاله15,799,293
علمبردار میبدی, محسن, هاشمی, افشان. (1403). لم بلاباس: تحلیل، کاربرد و الگوریتم. , 9(2), 1-18. doi: 10.22108/msci.2024.139150.1606
محسن علمبردار میبدی; افشان هاشمی. "لم بلاباس: تحلیل، کاربرد و الگوریتم". , 9, 2, 1403, 1-18. doi: 10.22108/msci.2024.139150.1606
علمبردار میبدی, محسن, هاشمی, افشان. (1403). 'لم بلاباس: تحلیل، کاربرد و الگوریتم', , 9(2), pp. 1-18. doi: 10.22108/msci.2024.139150.1606
علمبردار میبدی, محسن, هاشمی, افشان. لم بلاباس: تحلیل، کاربرد و الگوریتم. , 1403; 9(2): 1-18. doi: 10.22108/msci.2024.139150.1606

لم بلاباس: تحلیل، کاربرد و الگوریتم

نشریه ریاضی و جامعه
مقاله 2، دوره 9، شماره 2، شهریور 1403، صفحه 1-18    اصل مقاله (1.62 M)
نوع مقاله: مقاله پژوهشی
شناسه دیجیتال (DOI): 10.22108/msci.2024.139150.1606
نویسندگان
محسن علمبردار میبدی* 1؛ افشان هاشمی2
1گروه ریاضی کاربردی و علوم کامپیوتر، دانشکده ریاضی و آمار، دانشگاه اصفهان
2گروه کامپیوتر و علوم اطلاعات، دانشگاه لینشوپینگ، سوئد
چکیده
بسیاری از قضایا‌یی که در دهه‌های ۶۰ و ۷۰ میلادی در ترکیبیات و نظریه‌ی گراف توسط پژوهشگران توسعه داده شده‌اند، امروزه در طراحی الگوریتم‌ها و حل مسائل جدید همچنان کاربرد دارد. هدف این مقاله این است که نشان دهیم چیزهای مفیدی در گذشته رخ داده است که نباید آنها را فراموش کنیم و باید با نگاهی خلاقانه از آنها استفاده کنیم. لم بلاباس، که در دهه 1970 مطرح شد یک مسئله معروف در حوزه ترکیبیات است. در این مسئله، یک خانواده از مجموعه‌های $A_1, A_2,\ldots,A_m$ هر کدام با اندازه $a$ و خانواده‌ای دیگر از ‌مجموعه‌ها $B_1, B_2,\ldots,B_m$ هر کدام با اندازه $b$ داریم. هدف یافتن بیشترین مقدار $m$ از تعداد مجموعه‌ها است به‌طوری‌که برای هر اندیس $i$ داشته باشیم $A_i\cap B_i = \emptyset$ و همچنین $A_i\cap B_j \neq \emptyset$، برای هر $i \neq j$. لم بلاباس کران بالایی برای حداکثر تعداد این مجموعه‌ها به‌صورت $m\leq \binom{a+b}{b} $ بیان می‌کند. در این مقاله، پس از بیان حالات لم و اثبات موجود برای این لم، اثبات دیگری بر پایه احتمال برای لم بلاباس ارائه می‌دهیم و سپس با نگاهی متفاوت به این مسئله ترکیبیاتی، به بررسی کاربردهای جالب این لم در مسائل نظریه گراف و الگوریتم‌های پارامتری می‌پردازیم.
کلیدواژه‌ها
لم بلاباس؛ الگوریتم پارامتری؛ مجموعه معرف
سایر فایل های مرتبط با مقاله
مراجع

[1] B. Bollobás, On generalized graphs, Acta Math. Acad. Sci. Hungar., 16 (1965) 447–452.
[2] B. Bollobás, The art of mathematics. Coffee time in Memphis, Cambridge University Press, New York, 2006.
[3] C. Bey, Polynomial LYM inequalities, Combinatorica, 25 no. 1 (2005) 19–38.
[4] F. V. Fomin and P. Kaski, Exact exponential algorithms, Communications of the ACM, 56 no. 3 (2013) 80–88.
[5] L. Lovász, Flats in matroids and geometric graphs, Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Academic Press, London-New York, (1977) 45–86.
[6] M. Naor, L. J. Schulman and A. Srinivasan, Splitters and near-optimal derandomization, InProceedings of IEEE 36th Annual Foundations of Computer Science, (1995) 182–191.
[7] M. Cygan, F. V. Fomin, L. Kowalik ,D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized algorithms, Springer (2015).

آمار
تعداد مشاهده مقاله: 558
تعداد دریافت فایل اصل مقاله: 397


سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب