Title of article
An algorithm for online topological ordering
Author/Authors
Ajwani، نويسنده , , Deepak and Friedrich، نويسنده , , Tobias and Meyer، نويسنده , , Ulrich، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2006
Pages
6
From page
7
To page
12
Abstract
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 ( n 2.75 ) time, independent of the number of edges m inserted. For dense DAGs, this is an improvement over the previous best result of O ( min { m 3 2 log n , m 3 2 + n 2 log n } ) Katriel and Bodlaender.
Keywords
graph algorithms , topological ordering , online algorithms
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2006
Journal title
Electronic Notes in Discrete Mathematics
Record number
1454325
Link To Document