# MPI-I-93-119

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

Acknowledgement:** **

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.pdf | 7032 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: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-119

**BibTeX**
`@TECHREPORT{``HagerupMaas93``,`

` 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},`

`}`