کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426731 686250 2016 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Topology recognition with advice
ترجمه فارسی عنوان
تشخیص توپولوژی با مشاوره
کلمات کلیدی
تشخیص توپولوژی؛ شبکه؛ مشاوره؛ زمان؛ معاوضه
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

In topology recognition, each node of an anonymous network has to deterministically produce an isomorphic copy of the underlying graph, with all ports correctly marked. This task is usually unfeasible without any a priori information. Such information can be provided to nodes as advice. An oracle knowing the network can give a (possibly different) string of bits to each node, and all nodes must reconstruct the network using this advice, after a given number of rounds of communication. During each round each node can exchange arbitrary messages with all its neighbors and perform arbitrary local computations. The time of completing topology recognition is the number of rounds it takes, and the size of advice is the maximum length of a string given to nodes.We investigate tradeoffs between the time in which topology recognition is accomplished and the minimum size of advice that has to be given to nodes. We provide upper and lower bounds on the minimum size of advice that is sufficient to perform topology recognition in a given time, in the class of all graphs of size n   and diameter D≤αnD≤αn, for any constant α<1α<1. In most cases, our bounds are asymptotically tight.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 247, April 2016, Pages 254–265
نویسندگان
, , ,