سایپرز، باشگاه دانش - ارائه دهنده مقالات ژورنالهای خارجی

اطلاعات و مشخصات مقاله

explorer iconلينك‌ها

[ بازگشت | جستجو | فهرست کلمات کلیدی | فهرست موضوعات | فهرست نویسندگان | فهرست ناشران | فهرست ژورنالها ]

info iconاطلاعات مقاله

[ 31 بار مشاهده چكيده]

عنوان مقاله:سریع اکتشاف مشترک گراف
ناشر: [ Elsevier BV ]
ژورنال
دوره (شماره): (0)
سال انتشار:August 2015
شماره صفحات: 374937-49
نشانگر دیجیتالی شیء:[ 10.1016/j.ic.2014.12.005 ]
شما اینجا هستید:
  1. Scipers, the Knowledge ClubScipers »
  2. Elsevier BV »
  3. Information And Computation »
  4. Fast collaborative graph exploration

report iconنمايش خلاصه مقاله

Fast Collaborative Graph Exploration


مقاله: سریع اکتشاف مشترک گراف

نويسند‌گان:


خلاصه مقاله:


We study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. We ask how many time steps are required to complete exploration, i.e., to make sure that every vertex has been visited by some agent.As our main result, we provide the first strategy which performs exploration of a graph with n vertices at a distance of at most D from r in time O(D), using a team of agents of polynomial size k=Dn1+ϵ0. Our strategy works in the local communication model, in which agents can only exchange information when located at a vertex, without knowledge of global parameters such as n or D.We also obtain almost-tight bounds on the asymptotic relation between exploration time and team size, for large k, in both the local and the global communication model.


ما مطالعه سناریوی زیر از اکتشاف آنلاین گراف. گروهی از عوامل K است ابتدا در یک تحقیق راس برجسته گراف بدون جهت واقع شده است. ما از چند مرحله زمان مورد نیاز برای تکمیل اکتشاف، به عنوان مثال، مطمئن شوید که هر راس شده است توسط برخی agent.As بازدید نتیجه اصلی ما، ما شما را به اولین استراتژی که به انجام اکتشاف یک گراف با n راس در فاصله در اکثر D از R در زمان O (D)، با استفاده از یک تیم از ماموران از اندازه چند جمله ای k = Dn1 ε<n2 ϵ, for="" any="" ϵ="">0. استراتژی ما کار می کند در مدل ارتباطات از قسمت محلی، که در آن عوامل، تنها می تواند تبادل اطلاعات در هنگامی که در رأس قرار گرفته است، بدون اطلاع از پارامترهای جهانی مانند N و یا D.We نیز مرزهای تقریبا تنگ در رابطه مجانبی بین زمان اکتشاف و بدست آوردن اندازه، برای k بزرگ، در هر دو محلی و مدل ارتباطات جهانی است. </n2 ϵ,>


كلمات كليدي:




موضوعات:

Theoretical Computer Science, Computational Theory and Mathematics, Information Systems, Computer Science Applications



[ ]

 

دسترسی بین المللی

اگر شما در داخل کشور (ایران) هستید و این صفحه را مشاهده می کنید، نشان می دهد که IP شما به هر دلیلی در لیست IP های ایران ثبت نشده است. برای رفع این مشکل کافی است IP خود را که در پایین این پیام درج شده از طریق آدرس ایمیل support@scipers.com به ما اطلاع دهید. پس از دریافت درخواست، کارشناسان فنی موضوع را بررسی می نمایند و در صورتی که محل اتصال شما از کشور ایران بوده باشد، به لیست استفاده کنندگان مجاز افزوده می شوید.
IP: 34.234.76.59

اطلاعات استنادی

اطلاعات استنادی این مقاله را به نرم افزارهای مدیریت اطلاعات علمی و استنادی ارسال نمایید و در تحقیقات خود از آن استفاده نمایید.

 

به اشتراک گذاری

این صفحه را با استفاده از انواع شبکه های اجتماعی با دوستان خود به اشتراک بگذارید.

برگشت به بالا
رونمایی از اولین و تنها ربات تلگرامی جستجوی مقالات ژورنالی
×