On the complexity of topological sorting

DOI10.1016/0020-0190(90)90050-8MaRDI QIDQ750150zbMATHOpenAlexFDO

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

zbMATH Keywords

computational complexityparallel algorithmsacyclic digraphNL-hardtopological sorting

Mathematics Subject Classification ID

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)

Recommendations

• 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

Cites work

• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• Nondeterministic Space is Closed under Complementation
• Parallel Matrix and Graph Algorithms
• Problems complete for deterministic logarithmic space
• Space-bounded reducibility among combinatorial problems

Cited in

(10)

• Thick 2D relations for document understanding
• 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?)
• More efficient topological sort using reconfigurable optical buses
• scientific article; zbMATH DE number 7376042 (Why is no real title available?)
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• On a theorem of Razborov
• Engineering a Topological Sorting Algorithm for Massive Graphs
• Topological sorts on DAGs

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)