Parallel algorithms for a class of graphs generated recursively
type: Item
instance of: scholarly article
title: Parallel algorithms for a class of graphs generated recursively
zbMATH Open document ID: 0691.68080
DOI: 10.1016/0020-0190(89)90199-3
author: Wojciech Rytter
author: Tomasz Szymacha
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: A star graph (G,R) is a kernel graph G and a set of additional pending edges R called legs each having exactly one common vertex with G. The vertices of G are labelled by a terminal and nonterminal symbols. A grammar is given by an axiom star graph \(X_ 0\) with no legs and a set of production \(X\to Y\). Here X is a star graph, whose kernel consists of only one vertex labelled by a nonterminal, and Y is a star graph with the same number of legs as X. The language of graphs defined by such a grammar is the set of all graphs (with only terminal labels) which are derivable from \(X_ 0\) by using the productions. Let \(NC^ i\) be the class of problems coumputable by a parallel random access machine. Then, recognition and parsing of graphs generated by such a grammar is i \(NC^ 2\), and several NP-complete problems are in \(NC^ 1\), if the parsing tree is given.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4131695
zbMATH Keywords: graph grammar
zbMATH Keywords: NC
zbMATH Keywords: NP-completeness
reviewed by: Jürgen Ebert
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90199-3
OpenAlex ID: W2070146374
cites work: Parallelism in random access machines
cites work: Q3992991
cites work: Parallel O(log n) time edge-colouring of trees and Halin graphs
cites work: Tree-like parse and polynomial subclasses of search problems
cites work: Q3759947
cites work: Q3700838
cites work: Q5753770
cites work: On efficient parallel computations for some dynamic programming problems
cites work: On the complexity of parallel parsing of general context-free languages
cites work: Parallel time O(log n) recognition of unambiguous context-free languages
cites work: Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
description: scientific article; zbMATH DE number 4131695