کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871792 | 1440191 | 2017 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Eccentricity approximating trees
ترجمه فارسی عنوان
محدوده تقریبی درختان
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Using the characteristic property of chordal graphs that they are the intersection graphs of subtrees of a tree, Erich Prisner showed that every chordal graph admits an eccentricity 2-approximating spanning tree. That is, every chordal graph G has a spanning tree T such that eccT(v)âeccG(v)â¤2 for every vertex v, where eccG(v) (eccT(v)) is the eccentricity of a vertex v in G (in T, respectively). Using only metric properties of graphs, we extend that result to a much larger family of graphs containing among others chordal graphs, the underlying graphs of 7-systolic complexes and plane triangulations with inner vertices of degree at least 7. Furthermore, based on our approach, we propose two heuristics for constructing eccentricity k-approximating trees with small values of k for general unweighted graphs. We validate those heuristics on a set of real-world networks and demonstrate that all those networks have very good eccentricity approximating trees.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 232, 11 December 2017, Pages 142-156
Journal: Discrete Applied Mathematics - Volume 232, 11 December 2017, Pages 142-156
نویسندگان
Feodor F. Dragan, Ekkehard Köhler, Hend Alrasheed,