کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431654 688602 2012 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Testing connectivity of faulty networks in sublinear time
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Testing connectivity of faulty networks in sublinear time
چکیده انگلیسی

Given a set F of vertices of a connected graph G  , we study the problem of testing the connectivity of G−FG−F in polynomial time with respect to |F||F| and the maximum degree Δ of G  . We present two approaches. The first algorithm for this problem runs in O(|F|Δ2ε−1log(|F|Δε−1))O(|F|Δ2ε−1log(|F|Δε−1)) time for every graph G   with vertex expansion at least ε>0ε>0. The other solution, designed for the class of graphs with cycle basis consisting of cycles of length at most l  , leads to O(|F|Δ⌈l/2⌉log(|F|Δ⌊l/2⌋))O(|F|Δ⌈l/2⌉log(|F|Δ⌊l/2⌋)) running time. We also present an extension of this method to test the biconnectivity of G−FG−F in O(|F|Δllog(|F|Δl))O(|F|Δllog(|F|Δl)) time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 14, July 2012, Pages 223–231
نویسندگان
, , , , ,