scientific article; zbMATH DE number 4053039

zbMATH Open0645.68074MaRDI QIDQ3789084FDOQ3789084

Authors: Clemens Lautemann 

Publication date: 1988

Title of this publication is not available (Why is that?)

Recommendations

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

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)

Cited In (23)

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• A partial k-arboretum of graphs with bounded treewidth
• Title not available (Why is that?)
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• The complexity of graph languages generated by hyperedge replacement
• A Greibach normal form for context-free graph grammars
• A generic approach to decomposition algorithms, with an application to digraph decomposition
• Incremental and Efficient Computation of Families of Component Trees
• Recognising \(k\)-connected hypergraphs in cubic time
• Graph-theoretic properties compatible with graph derivations
• Context-free hypergraph grammars have the same term-generating power as attribute grammars
• The translation power of top-down tree-to-graph transducers
• Tree decomposition
• The monadic second-order logic of graphs : Definable sets of finite graphs
• On hyperedge replacement and BNLC graph grammars
• 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)