Publication:3789084
From MaRDI portal
zbMath0645.68074MaRDI QIDQ3789084
Publication date: 1988
NP-complete; polynomial time; data structure; graph languages; context-free graph grammars; bounded label size; decomposition trees; edge replacement grammars
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68R10: Graph theory (including graph drawing) in computer science
68P05: Data structures
Related Items
Unnamed Item, Algorithmic uses of the Feferman-Vaught theorem, Characterization and complexity of uniformly nonprimitive labeled 2-structures, Recognising \(k\)-connected hypergraphs in cubic time, Metatheorems for decision problems on hyperedge replacement graph languages, The string generating power of context-free hypergraph grammars, Context-free hypergraph grammars have the same term-generating power as attribute grammars, A partial k-arboretum of graphs with bounded treewidth, On hyperedge replacement and BNLC graph grammars, The translation power of top-down tree-to-graph transducers, Generating irregular partitionable data structures, The complexity of graph languages generated by hyperedge replacement