کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414762 681030 2013 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time
چکیده انگلیسی

Let G be an n-vertex planar, undirected, and unweighted graph. It was stated as open problems whether the Wiener index, defined as the sum of all-pairs shortest path distances, and the diameter of G   can be computed in o(n2)o(n2) time. We show that both problems can be solved in O(n2loglogn/logn) time with O(n)O(n) space. The techniques that we apply allow us to build, within the same time bound, an oracle for exact distance queries in G  . More generally, for any parameter S∈[(logn/loglogn)2,n2/5], distance queries can be answered in O(SlogS/logn) time per query with O(n2/S) preprocessing time and space requirement. With respect to running time, this is better than previous algorithms when logS=o(logn). All algorithms have linear space requirement. Our results generalize to a larger class of graphs including those with a fixed excluded minor.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 7, October 2013, Pages 831–838
نویسندگان
,