1. Testing connectivity of faulty networks in sublinear time.
- Author
-
Dvořák, Tomáš, Fink, Jiří, Gregor, Petr, Koubek, Václav, and Radzik, Tomasz
- Subjects
GRAPH connectivity ,FAULT-tolerant computing ,PATHS & cycles in graph theory ,POLYNOMIALS ,GRAPH theory ,TOPOLOGICAL degree ,MATHEMATICAL analysis - Abstract
Abstract: 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. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF