Average-case analysis of incremental topological ordering
Files in This Item:
|ajwani_dam10_before_copyright.pdf||237.66 kB||Adobe PDF||Download|
|Title:||Average-case analysis of incremental topological ordering||Authors:||Ajwani, Deepak
|Permanent link:||http://hdl.handle.net/10197/10132||Date:||28-Feb-2010||Online since:||2019-04-24T13:00:26Z||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 O(n2polylog(n)) under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (1990) , Katriel and Bodlaender (2006) , and Pearce and Kelly.||Type of material:||Journal Article||Publisher:||Elsevier||Journal:||Discrete Applied Mathematics||Volume:||158||Issue:||4||Start page:||240||End page:||250||Copyright (published version):||2009 Elsevier||Keywords:||Dynamic graph algorithms; Average-case analysis; Random graphs||DOI:||10.1016/j.dam.2009.07.006||Language:||en||Status of Item:||Peer reviewed|
|Appears in Collections:||Computer Science Research Collection|
Show full item record
This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.