کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949974 | 1440208 | 2016 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fast approximation for computing the fractional arboricity and extraction of communities of a graph
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we develop some algorithmic aspects of the fractional arboricity of a graph in order to study some new approaches for graph clustering. For a given undirected graph G(V,E) with m edges and n vertices, the fractional arboricity γ(G) measures the maximum edge density of the subgraphs of G(V,E). It is the fractional covering number of the corresponding graphic matroid. The fractional arboricity, for applications in networks reliability or the approximation of the chromatic number of the graphs, has been studied for many years. There are some algorithms in polynomial time to compute the fractional arboricity and its integer part. But, for large graphs such as the graph of the Web or graphs of social networks, the exact algorithms are not fast enough for practical use. That is why we describe a new FPTAS to compute an ε-approximation of the fractional arboricity (with ε>0 as small as desired). Our algorithm uses the principle of the multiplicative weights update method, needs a memory of size O(m) and has a complexity of O(mlog2(m)log(mn)/ε2). We also give a 2-approximation of γ(G) with computation time O(m), which is a quick preprocessing for the main algorithm. Finally, we present a fast algorithm to extract a subgraph which achieves the value of the approximation of the fractional arboricity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 213, 20 November 2016, Pages 179-195
Journal: Discrete Applied Mathematics - Volume 213, 20 November 2016, Pages 179-195
نویسندگان
Bio Mikaila Toko Worou, Jérôme Galtier,