Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Generalized topological sorting in linear time

Hagerup, Torben and Maas, Martin

MPI-I-93-119. May 1993, 10 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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)$.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-93-119.pdfMPI-I-93-119.pdf7032 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Hagerup, Torben and Maas, Martin},
  TITLE = {Generalized topological sorting in linear time},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-93-119},
  MONTH = {May},
  YEAR = {1993},
  ISSN = {0946-011X},