کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431365 | 688513 | 2009 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Yet another optimal algorithm for 3-edge-connectivity
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
An optimal algorithm for 3-edge-connectivity is presented. The algorithm performs only one pass over the given graph to determine a set of cut-pairs whose removal leads to the 3-edge-connected components. An additional pass determines all the 3-edge-connected components of the given graph. The algorithm is simple, easy to implement and runs in linear time and space. Experimental results show that it outperforms all the previously known linear-time algorithms for 3-edge-connectivity in determining if a given graph is 3-edge-connected and in determining cut-pairs. Its performance is also among the best in determining the 3-edge-connected components.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 7, Issue 1, March 2009, Pages 130–146
Journal: Journal of Discrete Algorithms - Volume 7, Issue 1, March 2009, Pages 130–146
نویسندگان
Yung H. Tsin,