کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328728 | 684878 | 2005 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Distance labeling schemes for well-separated graph classes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices can be inferred from inspecting their labels. It is shown in this paper that the classes of interval graphs and permutation graphs enjoy such a distance labeling scheme using O(log2n) bit labels on n-vertex graphs. Towards establishing these results, we present a general property for graphs, called well-(α,g)-separation, and show that graph classes satisfying this property have O(g(n)logn) bit labeling schemes. In particular, interval graphs are well-(2,logn)-separated and permutation graphs are well-(6,logn)-separated.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 145, Issue 3, 30 January 2005, Pages 384-402
Journal: Discrete Applied Mathematics - Volume 145, Issue 3, 30 January 2005, Pages 384-402
نویسندگان
Michal Katz, Nir A. Katz, David Peleg,