The lexicographically first topological order problem is NLOG-complete

DOI10.1016/0020-0190(89)90189-0MaRDI QIDQ582104zbMATH OpenOpenAlexFDO

Authors Takayoshi Shoudai

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90189-0

zbMATH Keywords

computational complexityNLOG-completetopological sort

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A parallelizable lexicographically first maximal edge-induced subgraph problem
• A taxonomy of problems with fast parallel algorithms
• Depth-first search is inherently sequential
• scientific article; zbMATH DE number 4047154 (Why is no real title available?)
• scientific article; zbMATH DE number 4060745 (Why is no real title available?)
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 65738 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Nondeterministic Space is Closed under Complementation
• Parallel Matrix and Graph Algorithms
• Parallelism and the maximal path problem

Cited in

(1)

• On the complexity of topological sorting

This page was built for publication: The lexicographically first topological order problem is NLOG-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q582104)