Treewidth and logical definability of graph products

DOI10.1016/J.TCS.2008.10.019zbMath1162.68023OpenAlexW2028144236MaRDI QIDQ1006041

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

path-decompositiongraph grammarstree-decompositiongraph logic

Mathematics Subject Classification ID

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

Related Items (3)

Treewidth of Cartesian Products of Highly Connected Graphs ⋮ Bandwidth and pathwidth of three-dimensional grids ⋮ Lower bounds for treewidth of product graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Basic notions of universal algebra for language theory and graph grammars
• The structure of the models of decidable monadic theories of graphs
• Triangulating graphs without asteroidal triples
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
• Graph expressions and graph rewritings
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Handbook of Graph Grammars and Computing by Graph Transformation
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

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