Parallel algorithms for a class of graphs generated recursively

DOI10.1016/0020-0190(89)90199-3zbMath0691.68080OpenAlexW2070146374MaRDI 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

zbMATH Keywords

NP-completenessgraph grammarNC

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Parallel algorithms for a class of graphs generated recursively