Publikace na Matematicko-fyzikální fakulta |
2011
Abstrakt
Given a connected graph G and a set F of faulty vertices of G, let G − F be the graph obtained from G by deletion of all vertices of F and edges incident with them. Is there an algorithm, whose running time may be bounded by a polynomial function of |F| and log |V(G)|, which decides whether G − F is still connected? Even though the answer to this question is negative in general, we describe an algorithm which resolves this problem for the n-dimensional hypercube in time O(|F|n^3).
Furthermore, we sketch a more general algorithm that is efficient for graph classes with good vertex expansion properties.