Average-case analysis of incremental topological ordering |
| |
Authors: | Deepak Ajwani |
| |
Institution: | a Center for Massive Data Algorithmics, Aarhus, Denmark b International Computer Science Institute, Berkeley, CA 94704, USA |
| |
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 updates. 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 under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (1990) 4], Katriel and Bodlaender (2006) 18], and Pearce and Kelly (2006) 23]. |
| |
Keywords: | Dynamic graph algorithms Average-case analysis Random graphs |
本文献已被 ScienceDirect 等数据库收录! |
|