On the complexity of topological sorting
DOI10.1016/0020-0190(90)90050-8zbMATH Open0713.68025OpenAlexW2043398952MaRDI QIDQ750150FDOQ750150
Authors: Seinosuke Toda 
Publication date: 1990
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(90)90050-8
Recommendations
- A topological sorting algorithm for large graphs
- scientific article; zbMATH DE number 3958742
- scientific article
- 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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
Cited In (10)
- Thick 2D relations for document understanding
- An O ( n 2.75 ) algorithm for incremental topological ordering
- Title not available (Why is that?)
- Title not available (Why is that?)
- Engineering a Topological Sorting Algorithm for Massive Graphs
- Topological sorts on DAGs
- On a theorem of Razborov
- More efficient topological sort using reconfigurable optical buses
- Title not available (Why is that?)
- Title not available (Why is that?)
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)
