کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434075 | 689678 | 2015 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Distinguishing views in symmetric networks: A tight lower bound
ترجمه فارسی عنوان
دیدگاه های متفاوتی در شبکه های متقارن: مرز پایین تنگ
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شبکه ناشناس شبکه با برچسب بندری چشم انداز، نمودار تقسیم
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers n≥D≥1n≥D≥1, there exists a port-labeled network with at most n nodes and diameter at most D which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth Ω(Dlog(n/D))Ω(Dlog(n/D)) are identical.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 582, 31 May 2015, Pages 27–34
Journal: Theoretical Computer Science - Volume 582, 31 May 2015, Pages 27–34
نویسندگان
Dariusz Dereniowski, Adrian Kosowski, Dominik Pająk,