Affordable Access

An $\tilde{O}(n^{2.5})$-Time Algorithm for Online Topological Ordering

Authors
  • Liu, Hsiao-Fei
  • Chao, Kun-Mao
Type
Preprint
Publication Date
Aug 23, 2008
Submission Date
Apr 24, 2008
Source
arXiv
License
Yellow
External links

Abstract

We present an $\tilde{O}(n^{2.5})$-time algorithm for maintaining the topological order of a directed acyclic graph with $n$ vertices while inserting $m$ edges.

Report this publication

Statistics

Seen <100 times