Parallel algorithms for a class of graphs generated recursively (Q582922): Difference between revisions
From MaRDI portal
Latest revision as of 11:56, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parallel algorithms for a class of graphs generated recursively |
scientific article |
Statements
Parallel algorithms for a class of graphs generated recursively (English)
0 references
1989
0 references
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.
0 references
graph grammar
0 references
NC
0 references
NP-completeness
0 references