Equivalent definitions of recognizability for sets of graphs of bounded tree-width

DOI10.1017/S096012950000092XMaRDI QIDQ4882496zbMATH OpenFDO

Authors Jens Lagergren, Bruno Courcelle

Publication date 12 September 1996

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

zbMATH Keywords

finite graphstree-width

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Recognizable sets of graphs of bounded tree-width
• scientific article; zbMATH DE number 1136093
• Recognizable sets of graphs: equivalent definitions and closure properties
• Definability equals recognizability for graphs of bounded treewidth
• The recognizability of sets of graphs is a robust property

Cites work

• Algebraic automata and context-free sets
• An algebraic theory of graph reduction
• Easy problems for tree-decomposable graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(14)

• scientific article; zbMATH DE number 7471715 (Why is no real title available?)
• Recognizable sets of graphs: equivalent definitions and closure properties
• scientific article; zbMATH DE number 7204410 (Why is no real title available?)
• scientific article; zbMATH DE number 7651203 (Why is no real title available?)
• Recognizability equals definability for partial k-paths
• Recognizable sets of graphs of bounded tree-width
• Recognizability, hypergraph operations, and logical types
• A linear fixed parameter tractable algorithm for connected pathwidth
• Computing Tree Decompositions
• Definability equals recognizability for graphs of bounded treewidth
• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• On computing graph minor obstruction sets
• The recognizability of sets of graphs is a robust property
• Bicycles and Spanning Trees

This page was built for publication: Equivalent definitions of recognizability for sets of graphs of bounded tree-width

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