# Item

ITEM ACTIONSEXPORT

Released

Report

#### Generalized topological sorting in linear time

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-93-119.pdf

(Any fulltext), 7MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B74A-8

##### Abstract

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)$.