Treewidth and logical definability of graph products

DOI10.1016/J.TCS.2008.10.019MaRDI QIDQ1006041zbMATH OpenOpenAlexFDO

Authors Selma Djelloul

Publication date 17 March 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.10.019

zbMATH Keywords

graph grammarsgraph logicpath-decompositiontree-decomposition

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Graph decompositions for cartesian products
• Treewidth of Cartesian products of highly connected graphs
• Definability equals recognizability for graphs of bounded treewidth
• scientific article; zbMATH DE number 1136093
• Tree-width of product of a connected graph and a k-connected partial k-tree

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Basic notions of universal algebra for language theory and graph grammars
• Graph expressions and graph rewritings
• Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
• Handbook of Graph Grammars and Computing by Graph Transformation
• scientific article; zbMATH DE number 475615 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 772777 (Why is no real title available?)
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The structure of the models of decidable monadic theories of graphs
• Triangulating graphs without asteroidal triples

Cited in

(6)

• Graph decompositions for cartesian products
• Definability equals recognizability for graphs of bounded treewidth
• Treewidth of Cartesian products of highly connected graphs
• Bandwidth and pathwidth of three-dimensional grids
• Structural properties of graph products
• Lower bounds for treewidth of product graphs

This page was built for publication: Treewidth and logical definability of graph products

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