If a digraph is acyclic (has no directed cycles), a polynomial sequential algorithm can perform a topological sort on its vertices - that is, label them 1,2,...,n so that arcs go only from vertices with smaller labels to vertices with larger labels. The parallel complexity of this problem has been successively reduced from \(NC^ 2\) to \(NL^*\) to \(FL^{NL}\) [see \textit{S. A. Cook}, Inf. Control 64, 2-22 (1985; Zbl 0575.68045) for definitions of parallel complexity classes]. In Cook [loc. cit.] the problem was posed as to whether this problem is NL (non-deterministic log-space)-hard under \(NC^ 1\)-reducibility and answered in the affirmative if the algorithm is required to state whether the digraph is acyclic (since deciding whether a digraph is acyclic is NL-hard) but left open otherwise. The author shows that topological sorting is NL-hard even if the algorithm is required merely to topologically sort a digraph which happens to be acyclic and is allowed to label its vertices arbitrarily otherwise. In case the graph has no cycles, directed or undirected, the article presents a DL (deterministic log-space) topological sorting algorithm. It was shown in \textit{S. A. Cook} and \textit{P. McKenzie} [J. Algorithms 8, 385-394 (1987; Zbl 0644.68058)] that deciding whether an undirected graph is acyclic is DL-complete; the article under review proves that topological sorting is DL-complete even if the algorithm is not required to state whether the underlying undirected graph is acyclic.
- A topological sorting algorithm for large graphs
- scientific article; zbMATH DE number 3958742
- scientific article; zbMATH DE number 5115639
- I/O-Efficient Algorithms for Topological Sort and Related Problems
- More efficient topological sort using reconfigurable optical buses
- Problems complete for deterministic logarithmic space
- I/O-efficient algorithms for topological sort and related problems
- Engineering a Topological Sorting Algorithm for Massive Graphs
- The lexicographically first topological order problem is NLOG-complete
- Depth-first search is inherently sequential
- A taxonomy of problems with fast parallel algorithms
- scientific article; zbMATH DE number 4087055 (Why is no real title available?)
- Nondeterministic Space is Closed under Complementation
- Parallel Matrix and Graph Algorithms
- Problems complete for deterministic logarithmic space
- Space-bounded reducibility among combinatorial problems
- More efficient topological sort using reconfigurable optical buses
- scientific article; zbMATH DE number 5115639 (Why is no real title available?)
- scientific article; zbMATH DE number 3958742 (Why is no real title available?)
- scientific article; zbMATH DE number 522854 (Why is no real title available?)
- On a theorem of Razborov
- Topological sorts on DAGs
- An O ( n 2.75 ) algorithm for incremental topological ordering
- scientific article; zbMATH DE number 7376042 (Why is no real title available?)
- Engineering a Topological Sorting Algorithm for Massive Graphs
- Thick 2D relations for document understanding
- Monoids of upper triangular matrices over the Boolean semiring
This page was built for publication: On the complexity of topological sorting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q750150)
