کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651550 | 1632578 | 2016 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A Simple Algorithm For Replacement Paths Problem
ترجمه فارسی عنوان
یک الگوریتم ساده برای مسیرهای تعویض مشکل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let G=(V,E)G=(V,E) (|V|=n|V|=n and |E|=m|E|=m) be an undirected graph with positive edge weights. Let PG(s,t)PG(s,t) be a shortest s−ts−t path in G. Let l be the number of edges in PG(s,t)PG(s,t). The Edge Replacement Path problem is to compute a shortest s−ts−t path in G\{e}G\{e}, for every edge e in PG(s,t)PG(s,t). The Node Replacement Path problem is to compute a shortest s−ts−t path in G\{v}G\{v}, for every vertex v in PG(s,t)PG(s,t).In this paper we present an O(TSPT(G)+m+l2)O(TSPT(G)+m+l2) time and O(m+l2)O(m+l2) space algorithm for both the problems. Where, TSPT(G)TSPT(G) is the asymptotic time to compute a single source shortest path tree in G. The proposed algorithm is simple and easy to implement.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 53, September 2016, Pages 307–318
Journal: Electronic Notes in Discrete Mathematics - Volume 53, September 2016, Pages 307–318
نویسندگان
Anjeneya Swami Kare,