Name
Abstract | ||
|---|---|---|
Given a set F of vertices of a connected graph G, we study the problem of testing the connectivity of G-F in polynomial time with respect to |F| and the maximum degree @D of G. We present two approaches. The first algorithm for this problem runs in O(|F|@D^2@e^-^1log(|F|@D@e^-^1)) time for every graph G with vertex expansion at least @e0. The other solution, designed for the class of graphs with cycle basis consisting of cycles of length at most l, leads to O(|F|@D^@?^l^/^2^@?log(|F|@D^@?^l^/^2^@?)) running time. We also present an extension of this method to test the biconnectivity of G-F in O(|F|@D^llog(|F|@D^l)) time. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.jda.2011.12.014 | J. Discrete Algorithms |
Keywords | Field | DocType |
set f,maximum degree,sublinear time,cycle basis,connected graph,graph g,polynomial time,testing connectivity,faulty network,vertex expansion,connectivity | Discrete mathematics,Graph,Sublinear time,Combinatorics,Vertex (geometry),Cycle basis,Vertex (graph theory),Degree (graph theory),Connectivity,Time complexity,Mathematics | Journal |
Volume | ISSN | Citations |
14, | 1570-8667 | 0 |
PageRank | References | Authors |
0.34 | 8 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tomáš Dvořák | 1 | 130 | 10.21 |
| Jiří Fink | 2 | 82 | 9.00 |
| Petr Gregor | 3 | 178 | 19.79 |
| Václav Koubek | 4 | 431 | 93.44 |
| Tomasz Radzik | 5 | 1098 | 95.68 |