AbstractThe 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, .., 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).
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory
Selected references
- Harold N. Gabow and Robert Endre Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30(2):209-221, April 1985.
- Witold Lipski Jr. and Franco P. Preparata. Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Informatica, 15:329-346, 1981.
- Wojciech Rytter. Context-free recognition via shortest paths computation: a version of Valiant's algorithm. Theoretical Computer Science, 143(2):343-352, 12 June 1995. Note.