Algorithm for incremental topological ordering

An O(n2.75) algorithm for incremental topological ordering DEEPAK AJWANI TOBIAS FRIEDRICH Max-Planck-Institut f¨ur Informatik, Germany and ULRICH MEYER J.W. Goethe University Frankfurt/Main, Germany We present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in O(n2.75) time, independent of the number m of edges inserted. For dense DAGs, this is an improvement over the previous best result of O(min{m32 logn,m32 + n2 logn}) by Katriel and Bodlaender.

We also provide an empirical comparison of our algorithm with other algorithms for incremental topological sorting. Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complex- ity]: Nonnumerical Algorithms and Problems—Computations on discrete structures; E.1 [Data Structures]: Graphs and networks; G.2.2 [Discrete Mathematics]: Graph Theory—Graph algorithms General Terms: Algorithms, Design, Theory Additional Key Words and Phrases: Dynamic algorithms, graphs, online algorithms, topological order 1. INTRODUCTION A topological order T of a given directed acyclic graph (DAG) G = (V,E) (with n := |V| and m := |E|) is a linear ordering of its nodes such that for all directed Research partially supported by DFG grant ME 2088/1-3, and by the center of massive data algorithmics (MADALGO) funded by the Danish National Research Foundation. A preliminary version of this article appeard in Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), volume 4059 of LNCS, pages 53–64, Springer, 2006. Authors’ addresses: D. Ajwani and T. Friedrich, Max-Planck-Institut f¨ur Informatik, Campus E1 4, 66123 Saarbr¨ucken, Germany, e-mail: firstname.lastname@mpi-inf.mpg.de; U. Meyer, In- stitute for Computer Science, J.W. Goethe University, 60325 Frankfurt/Main, Germany, e-mail: umeyer@cs.uni-frankfurt.de Permission to make digital/hard copy of all or part of this material without fee for personal or classroom use provided that the copies are not made or distributed for profit or commercial advantage, the ACM copyright/server notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists requires prior specific permission and/or a fee. c© 2008 ACM /2008/-0001 $5.00 2 · D. AJWANI, T. FRIEDRICH, and U. MEYER paths from x ∈ V to y ∈ V (x negationslash= y), it holds that T(x) < T(y). There exist well known algorithms for computing the topological ordering of a DAG in O(m+n) in an offline setting [Tarjan 1972; Knuth and Szwarcfiter 1974]. In the online variant of this problem, the edges of the DAG are not known in advance but are given one at a time. Each time an edge is added to the DAG, we are required to update the bijective mapping T. Incremental topological ordering is required for incremental evaluation of com- putational circuits [Alpern et al. 1990] and incremental compilation [Marchetti- Spaccamela et al. 1993; Omohundro et al. 1992] where a dependency graph between modules is maintained to...

Website: www.mpi-inf.mpg.de | Filesize: -
No of Page(s): 15
Download algorithm for incremental topological ordering - Max-Planck-Institut ....pdf