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

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