Technical, Research Report
@TechReport
Technischer-, Forschungsbericht


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:









Author, Editor

Author(s):

Katriel, Irit

dblp



Editor(s):





BibTeX Citekey*:

Katriel2004

Language:

English

Title, Institution

Title*:

On Algorithms for Online Topological Ordering and Sorting

Institution*:

Max-Planck-Institut für Informatik

Publishers or Institutions Address*:

Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany

Type:

Research Report

No, Year, pp.,

Number*:

MPI-I-2004-1-003

Pages*:

15

Month:

February

VG Wort
Pages*:


Year*:

2004

ISBN/ISSN:

0946-011X





DOI:




Note, Abstract, ©

Note:


(LaTeX) Abstract:

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.

Categories / Keywords:


Copyright Message:


HyperLinks / References / URLs:


Personal Comments:


File Upload:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat


BibTeX Entry:
@TECHREPORT{Katriel2004,
AUTHOR = {Katriel, Irit},
TITLE = {On Algorithms for Online Topological Ordering and Sorting},
PUBLISHER = {AG 1 - Mehlhorn},
YEAR = {2004},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut für Informatik},
NUMBER = {MPI-I-2004-1-003},
PAGES = {15},
ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
MONTH = {February},
ISBN = {0946-011X},
}


Entry last modified by Christine Kiesel, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Created
08/12/2005 12:13:30 PM
Revision
1.
0.


Editor
Christine Kiesel



Edit Date
12.08.2005 12:14:20



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
MPI-I-2004-1-003.ps
View attachments here: