Parallel algorithms for a class of graphs generated recursively
From MaRDI portal
Publication:582922
DOI10.1016/0020-0190(89)90199-3zbMath0691.68080MaRDI QIDQ582922
Wojciech Rytter, Tomasz Szymacha
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)90199-3
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68R10: Graph theory (including graph drawing) in computer science
03D15: Complexity of computation (including implicit computational complexity)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tree-like parse and polynomial subclasses of search problems
- On the complexity of parallel parsing of general context-free languages
- Parallel time O(log n) recognition of unambiguous context-free languages
- Parallel O(log n) time edge-colouring of trees and Halin graphs
- On efficient parallel computations for some dynamic programming problems
- Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
- Parallelism in random access machines