MPI-INF/SWS Research Reports 1991-2021

# MPI-I-93-119

## Generalized topological sorting in linear time

### Hagerup, Torben and Maas, Martin

#### May 1993, 10 pages.

.
##### Status: available - back from printing

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

URL to this document: https://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},
}