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

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