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

چکیده انگلیسی
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
Journal: Journal of Discrete Algorithms - Volume 14, July 2012, Pages 223–231
نویسندگان
Tomáš Dvořák, Jiří Fink, Petr Gregor, Václav Koubek, Tomasz Radzik,