کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949751 1364256 2017 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Scaling laws for maximum coloring of random geometric graphs
ترجمه فارسی عنوان
قوانین پوسته شدن برای حداکثر رنگ آمیزی نمودار های تصادفی هندسی
کلمات کلیدی
نمودار هندسی تصادفی رنگ آمیزی قوانین متضاد،
ترجمه چکیده
ما حداکثر رنگ ارگانی گرافیک هندسی تصادفی را در ابعاد دلخواه، اما ثابت با تعداد ثابت رنگها بررسی می کنیم. از آنجایی که این مسئله نه مقیاس ناپایدار و نه صاف، روش معمول برای به دست آوردن قوانین محدود نمی تواند اعمال شود. بنابراین ما مفاهیم متفاوتی را براساس زیرددی حساس می کنیم تا قوانین همگرایی برای حداکثر تعداد رأس ها که می توانند رنگ باشند، ایجاد کنیم. برای ثابت هایی که در این نتایج ظاهر می شوند، ما دقیق را در ابعاد 1 و مرزهای بالا و پایین در ابعاد بالاتر ارائه می دهیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
قوانین پوسته شدن برای حداکثر رنگ آمیزی نمودار های تصادفی هندسی
چکیده انگلیسی
We examine maximum vertex coloring of random geometric graphs, in an arbitrary but fixed dimension, with a constant number of colors. Since this problem is neither scale-invariant nor smooth, the usual methodology to obtain limit laws cannot be applied. We therefore leverage different concepts based on subadditivity to establish convergence laws for the maximum number of vertices that can be colored. For the constants that appear in these results, we provide the exact value in dimension one, and upper and lower bounds in higher dimensions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 217, Part 3, 30 January 2017, Pages 427-437
نویسندگان
, ,