کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9655159 | 684032 | 2005 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Self-spanner graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We introduce the (k,â)-self-spanners graphs to model non-reliable interconnection networks. Such networks can be informally characterized as follows: if at most â edges have failed, as long as two vertices remain connected, the distance between these vertices in the faulty graph is at most k times the distance in the non-faulty graph. By fixing the values k and â (called stretch factor and fault-tolerance, respectively), we obtain specific new graph classes. We first provide characterizational, structural, and computational results for these classes. Then, we study relationships between the introduced classes and special graphs classes (distance-hereditary graphs, cographs, and chordal graphs), and common network topologies (grids, tori, hypercubes, butterflies, and cube-connected cycles) as well.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 150, Issues 1â3, 1 September 2005, Pages 99-120
Journal: Discrete Applied Mathematics - Volume 150, Issues 1â3, 1 September 2005, Pages 99-120
نویسندگان
Serafino Cicerone, Gabriele Di Stefano, Dagmar Handke,