Average-Case Analysis of Incremental Topological Ordering

Average-Case Analysis of Incremental Topological Ordering Deepak Ajwani Tobias Friedrich Abstract Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic up- dates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average- case analysis of incremental topological ordering algorithms. We prove an expected runtime of u1D4AA(u1D45B2 polylog(u1D45B)) under insertion

of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (SODA, 1990), Katriel and Bodlaender (TALG, 2006), and Pearce and Kelly (JEA, 2006). 1 Introduction There has been a growing interest in dynamic graph algorithms over the last two decades due to their applications in a variety of contexts including operating systems, information systems, net- work management, assembly planning, VLSI design and graphical applications. Typical dynamic graph algorithms maintain a certain property (e.g., connectivity information) of a graph that changes (a new edge inserted or an existing edge deleted) dynamically over time. An algorithm or a problem is called fully dynamic if both edge insertions and deletions are allowed, and it is called partially dynamic if only one (either only insertion or only deletion) is allowed. If only insertions are allowed, the partially dynamic algorithm is called incremental; if only deletions are allowed, it is called decremental. While a number of fully dynamic algorithms have been obtained for various properties on undirected graphs (see [13] and references therein), the design and analysis of fully dynamic algorithms for directed graphs have turned out to be much harder (e.g., [16, 27–29]). Much of the research on directed graphs is therefore concentrated on the design of partially dy- namic algorithms instead (e.g., [5, 10, 18]). In this paper, we focus on the analysis of algorithms for maintaining a topological ordering of directed graphs in an incremental setting. For a directed graph u1D43A = (u1D449,u1D438) (with u1D45B := ∣u1D449∣ and u1D45A := ∣u1D438∣), a topological order u1D447 : u1D449 → [1..u1D45B] is a linear ordering of its nodes such that for all directed paths from u1D465 ∈ u1D449 to u1D466 ∈ u1D449 (u1D465 ∕= u1D466), it holds that u1D447(u1D465) < u1D447(u1D466). A directed graph has a topological ordering if and only if it is acyclic. There are well-known algorithms for computing the topological ordering of a directed acyclic graph (DAG) in u1D4AA(u1D45A+u1D45B) time in an offline setting (see e.g. [11]). In a fully dynamic setting, each time an edge is added or deleted from the DAG, we are required to update the bijective mapping u1D447. In the online/incremental variant of this problem, the edges of the DAG are not known in advance but are inserted one at a time (no deletions allowed). As the topological order remains valid when removing edges, most algorithms for online topological...

Website: www.mpi-inf.mpg.de | Filesize: -
No of Page(s): 14
Download Average-Case Analysis of Incremental Topological Ordering.pdf