کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9514600 | 1632609 | 2005 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Distance Labeling for Permutation Graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We show that every permutation graph with n elements can be preprocessed in O(n) time, if two linear extensions of the corresponding poset are given, to produce an O(n) space data-structure supporting distance queries in constant time. The data-structure is localized and given as a distance labeling, that is each vertex receives a label of O(log n) bits so that distance queries between any two vertices are answered by inspecting on their labels only. This result improves the previous scheme due to Katz, Katz and Peleg [M. Katz, N.A. Katz, and D. Peleg, Distance labeling schemes for well-separated graph classes, in 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS), H. Reichel and S. Tison, eds., vol. 1770 of Lecture Notes in Computer Science, Springer Verlag, Feb. 2000, pp. 516-528] in the STACS '00 by a log n factor.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 22, 15 October 2005, Pages 461-467
Journal: Electronic Notes in Discrete Mathematics - Volume 22, 15 October 2005, Pages 461-467
نویسندگان
Fabrice Bazzaro, Cyril Gavoille,