On the complexity of topological sorting

DOI10.1016/0020-0190(90)90050-8zbMath0713.68025OpenAlexW2043398952MaRDI QIDQ750150

No author found.

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) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

On a theorem of Razborov ⋮ Thick 2D relations for document understanding

Cites Work

• Unnamed Item
• Space-bounded reducibility among combinatorial problems
• A taxonomy of problems with fast parallel algorithms
• Problems complete for deterministic logarithmic space
• Nondeterministic Space is Closed under Complementation
• Parallel Matrix and Graph Algorithms

This page was built for publication: On the complexity of topological sorting