کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875640 | 1441978 | 2018 | 25 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Faster shortest paths in dense distance graphs, with applications
ترجمه فارسی عنوان
کوتاه ترین مسیر سریعتر در نمودارهای متراکم، با برنامه های کاربردی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This work is part of a research agenda that aims to develop new techniques that would lead to faster, possibly linear-time, algorithms for problems in planar graphs such as minimum-cut, maximum-flow, and shortest paths with negative arc lengths. As immediate applications, we show how to compute maximum flow in directed weighted planar graphs in O(nlogâ¡p) time, and minimum st-cut in undirected weighted planar graphs in O(nlogâ¡logâ¡p) time, where p is the minimum number of edges on any path from the source to the sink. We also show how to compute any part of the DDG that corresponds to a region with r vertices and k boundary vertices in O(rlogâ¡k) time, which is faster than has been previously known for small values of k.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 711, 8 February 2018, Pages 11-35
Journal: Theoretical Computer Science - Volume 711, 8 February 2018, Pages 11-35
نویسندگان
Shay Mozes, Yahav Nussbaum, Oren Weimann,