MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments

MPI-I-2004-1-003

On algorithms for online topological ordering and sorting

Katriel, Irit

February 2004, 15 pages.

.
Status: available - back from printing

We derive several results about algorithms for the online topological ordering and sorting problems. The main result is that a slight variation on an algorithm by Alpern et al. yields an amortized complexity of $\sqrt{m}\log n$ per edge for an $n$-node $m$-edge DAG. This is an improvement, for all except very dense graphs, over the best known previous result of $O(n)$ per edge due to Marchetti-Spaccamela et al.

  • MPI-I-2004-1-003.ps
  • Attachement: MPI-I-2004-1-003.ps (238 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2004-1-003

Hide details for BibTeXBibTeX
@TECHREPORT{Katriel2004,
  AUTHOR = {Katriel, Irit},
  TITLE = {On algorithms for online topological ordering and sorting},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2004-1-003},
  MONTH = {February},
  YEAR = {2004},
  ISSN = {0946-011X},
}