Average-case analysis of incremental topological ordering

Files in This Item:
File Description SizeFormat 
ajwani_dam10_before_copyright.pdf237.66 kBAdobe PDFDownload
Title: Average-case analysis of incremental topological ordering
Authors: Ajwani, Deepak
Friedrich, Tobias
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) [4], Katriel and Bodlaender (2006) [18], 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 algorithmsAverage-case analysisRandom 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

Citations 50

Last Week
Last month
checked on May 17, 2019

Google ScholarTM



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.