کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950863 | 1441035 | 2017 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on finding minimum mean cycle
ترجمه فارسی عنوان
یادداشت در پیدا کردن حداقل چرخه متوسط
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تجزیه و تحلیل الگوریتم ها، طراحی الگوریتم ها، الگوریتم های گراف،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In a directed graph with edge weights, the mean weight of a directed cycle is the weight of its edges divided by their number. The minimum cycle mean of the graph is the minimum mean weight of a cycle. Karp gave a characterization of minimum cycle mean and an O(nm) algorithm to compute it, where n is the number of vertices and m is the number of edges. However, an algorithm he suggested for identifying a cycle with this mean weight is not correct. We propose an alternative.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 127, November 2017, Pages 21-22
Journal: Information Processing Letters - Volume 127, November 2017, Pages 21-22
نویسندگان
Mmanu Chaturvedi, Ross M. McConnell,