scientific article; zbMATH DE number 4053039

MaRDI QIDQ3789084zbMATH OpenFDO

Authors Clemens Lautemann

Publication date 1988

zbMATH Keywords

data structureNP-completepolynomial timegraph languagescontext-free graph grammarsbounded label sizedecomposition treesedge replacement grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Recommendations

• A generic approach to decomposition algorithms, with an application to digraph decomposition
• scientific article; zbMATH DE number 4016952
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Algorithms finding tree-decompositions of graphs
• scientific article; zbMATH DE number 140151

Cited in

(25)

• scientific article; zbMATH DE number 6873974 (Why is no real title available?)
• scientific article; zbMATH DE number 1844471 (Why is no real title available?)
• Organizing the atoms of the clique separator decomposition into an atom tree
• Algorithmic uses of the Feferman-Vaught theorem
• The string generating power of context-free hypergraph grammars
• Metatheorems for decision problems on hyperedge replacement graph languages
• Algebras for tree decomposable graphs
• A partial k-arboretum of graphs with bounded treewidth
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• scientific article; zbMATH DE number 809155 (Why is no real title available?)
• The complexity of graph languages generated by hyperedge replacement
• A Greibach normal form for context-free graph grammars
• Incremental and Efficient Computation of Families of Component Trees
• A generic approach to decomposition algorithms, with an application to digraph decomposition
• Recognising \(k\)-connected hypergraphs in cubic time
• Context-free hypergraph grammars have the same term-generating power as attribute grammars
• Graph-theoretic properties compatible with graph derivations
• The translation power of top-down tree-to-graph transducers
• Tree decomposition
• On hyperedge replacement and BNLC graph grammars
• The monadic second-order logic of graphs : Definable sets of finite graphs
• Special data structures for problems on graphs associated with the notion of clique or with modular decomposition
• Generation of trees of a graph with the use of decomposition
• Generating irregular partitionable data structures
• Characterization and complexity of uniformly nonprimitive labeled 2-structures

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3789084)