Dynamic Transitive Closure Problems on Directed Graphs

Abstract

In this paper we survey the newest results for dynamic problems on directed graphs. In particular, we focus on the most fundamental problem, transitive closure. These problems play a crucial role in many applications, including network optimization and routing, traffic information systems, data bases, compilers.