Testing connectivity of faulty networks in sublinear time

详细信息	查看全文 | 推荐本文 |

• 作者：Tomá ; &scaron ; Dvo艡á ; k^a ; ^{Tomas.Dvorak@mff.cuni.cz} ; Ji艡í ; Fink^a ; ¹ ; Petr Gregor^a ; ² ; Vá ; clav Koubek^a ; ¹ ; Tomasz Radzik^b
• 关键词：Biconnectivity ; Connectivity ; Cycle basis ; Faulty vertex ; Interconnection network ; Vertex expansion
• 刊名：Journal of Discrete Algorithms
• 出版年：2012
• 期刊代码：10_15708667
• 类别：mt
• 出版时间：July, 2012
• 卷：14
• 期：Complete
• 页码：223-231
• 文件大小：203 K

摘要

Given a set F of vertices of a connected graph G, we study the problem of testing the connectivity of in polynomial time with respect to and the maximum degree 螖 of G. We present two approaches. The first algorithm for this problem runs in time for every graph G with vertex expansion at least . The other solution, designed for the class of graphs with cycle basis consisting of cycles of length at most l, leads to running time. We also present an extension of this method to test the biconnectivity of in time.