Generalized topological sorting in linear time
Torben Hagerup, Martin Maas · 1994
Abstract. The generalized topologica.l sorting problem takes a.s input a positive integer /c and a directed, acyclic graph with some vertices labded by positive integers, and the goa.l is to labd the remaining vertices by positive integers in such a way that each edge leads!rom a lower-Iabeled vertex to a higher-Iabded vertex, and such that the set of labds used is exactly {l,...,/c}. Given a generalized topologica.l sorting problem, we want to compute a solution, if one msts, and a.lso to test the unique-ness of a given solution. The best previous a.lgorithm for the generalized topologica.l sorting problem computes a solution, if one exists, and tests its uniqueness in O(nloglogn+m) time on input graphs with n vertices and m edges. We describe improved a.lgorithms that solve both problems in linear time O(n + m). 1