de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Generalized topological sorting in linear time

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44564

Hagerup,  Torben
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Maas,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-93-119.pdf
(beliebiger Volltext), 7MB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Hagerup, T., & Maas, M.(1993). Generalized topological sorting in linear time (MPI-I-93-119). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B74A-8
Zusammenfassung
The generalized topological sorting problem takes as input a positive integer $k$ and a directed, acyclic graph with some vertices labeled by positive integers, and the goal is to label the remaining vertices by positive integers in such a way that each edge leads from a lower-labeled vertex to a higher-labeled vertex, and such that the set of labels used is exactly $\{1,\ldots,k\}$. Given a generalized topological sorting problem, we want to compute a solution, if one exists, and also to test the uniqueness of a given solution. % The best previous algorithm for the generalized topological sorting problem computes a solution, if one exists, and tests its uniqueness in $O(n\log\log n+m)$ time on input graphs with $n$ vertices and $m$ edges. We describe improved algorithms that solve both problems in linear time $O(n+m)$.