ISSN:
1432-0541
Keywords:
Key words. Dynamic algorithms, Graph algorithms, Lookahead algorithms, Graph certificates, Sparsification, Strong connectivity, Transitive closure.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. Recent work in dynamic graph algorithms has led to efficient algorithms for dynamic undirected graph problems such as connectivity. However, no efficient deterministic algorithms are known for the dynamic versions of fundamental directed graph problems like strong connectivity and transitive closure, as well as some undirected graph problems such as maximum matchings and cuts. We provide some explanation for this lack of success by presenting quadratic lower bounds on the certificate complexity of the seemingly difficult problems, in contrast to the known linear certificate complexity for the problems which have efficient dynamic algorithms. In many applications of dynamic (di)graph problems, a certain form of lookahead is available. Specifically, we consider the problems of assembly planning in robotics and the maintenance of relations in databases. These give rise to dynamic strong connectivity and dynamic transitive closure problems, respectively. We explain why it is reasonable, and indeed natural and desirable, to assume that lookahead is available in these two applications. Exploiting lookahead to circumvent their inherent complexity, we obtain efficient dynamic algorithms for strong connectivity and transitive closure.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009220
Permalink
