The lexicographically first topological order problem is NLOG-complete
From MaRDI portal
Publication:582104
DOI10.1016/0020-0190(89)90189-0zbMath0689.68070MaRDI QIDQ582104
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
68Q25: Analysis of algorithms and problem complexity
68P10: Searching and sorting
03D15: Complexity of computation (including implicit computational complexity)
Cites Work
- Depth-first search is inherently sequential
- Parallelism and the maximal path problem
- A parallelizable lexicographically first maximal edge-induced subgraph problem
- A taxonomy of problems with fast parallel algorithms
- Nondeterministic Space is Closed under Complementation
- Parallel Matrix and Graph Algorithms
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item