کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871939 | 681683 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On computing the 2-vertex-connected components of directed graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we consider the problem of computing the 2-vertex-connected components of directed graphs. We present a new algorithm for solving this problem in O(nm) time. Furthermore, we show that the old algorithm of Erusalimskii and Svetlov runs in O(nm2) time. In this paper, we investigate the relationship between 2-vertex-connected components and dominator trees. We also consider three applications of our new algorithm, which are approximation algorithms for problems that are generalization of the problem of approximating the smallest 2-vertex-connected spanning subgraph of 2-vertex-connected directed graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 204, 11 May 2016, Pages 164-172
Journal: Discrete Applied Mathematics - Volume 204, 11 May 2016, Pages 164-172
نویسندگان
Raed Jaberi,