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

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

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


عنوان مقاله:سریع اکتشاف مشترک گراف
ناشر: [ 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

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

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

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

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

 

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

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

خلاصه مقاله، نویسندگان و کلمات کلیدی

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



[ ]

فهرست مقالات مرتبط و مشابه

  1. Dereniowski, Dariusz, Disser, Yann, Kosowski, Adrian, Pająk, Dominik, Uznański, Przemysław (2013) 'Fast Collaborative Graph Exploration', Automata, Languages, and Programming, Springer Nature, pp:520-532
  2. Brass, Peter, Cabrera-Mora, Flavio, Gasparri, Andrea, Jizhong Xiao, (2011) 'Multirobot Tree and Graph Exploration', IEEE Trans. Robot., Institute of Electrical & Electronics Engineers (IEEE), pp:707-717
  3. Fang, Meng , Yin, Jie , Zhu, Xingquan (2015) 'Active exploration for large graphs', Data Mining and Knowledge Discovery, Springer Science + Business Media, pp:0-0
  4. Ilcinkas, David (2006) 'Setting Port Numbers for Fast Graph Exploration', Structural Information and Communication Complexity, Springer Berlin Heidelberg, pp:59-69
  5. Ilcinkas, David (2008) 'Setting port numbers for fast graph exploration', Theoretical Computer Science, Elsevier BV, pp:236-242
  6. , , Klasing, Ralf, Martin, Russell, Navarra, Alfredo, Zhang, Xiaohui (2008) 'Fast periodic graph exploration with constant memory', Journal of Computer and System Sciences, Elsevier BV, pp:808-822
  7. Czumaj, Artur (2010) 'Local Graph Exploration and Fast Property Testing', Algorithms – ESA 2010, Springer Berlin Heidelberg, pp:410-414
  8. Khurana, Udayan, Parthasarathy, Srinivasan, Turaga, Deepak (2016) 'Graph-based exploration of non-graph datasets', Proceedings of the VLDB Endowment, VLDB Endowment, pp:1557-1560
  9. Shams, Bita, Haratizadeh, Saman (2017) 'Graph-based collaborative ranking', Expert Systems with Applications, Elsevier BV, pp:59-70
  10. Michailidis, George (2003) 'Visual exploration of data through their graph representations', Recent Advances and Trends in Nonparametric Statistics, Elsevier BV, pp:169-180

 

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