کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429951 | 687734 | 2006 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Planar graphs, negative weight edges, shortest paths, and near linear time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper, we present an O(nlog3n) time algorithm for finding shortest paths in an n-node planar graph with real weights. This can be compared to the best previous strongly polynomial time algorithm developed by Lipton, Rose, and Tarjan in 1978 which runs in O(n3/2) time, and the best polynomial time algorithm developed by Henzinger, Klein, Subramanian, and Rao in 1994 which runs in time. We also present significantly improved data structures for reporting distances between pairs of nodes and algorithms for updating the data structures when edge weights change.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 72, Issue 5, August 2006, Pages 868-889
Journal: Journal of Computer and System Sciences - Volume 72, Issue 5, August 2006, Pages 868-889