When Trees Grow Low: Shrubs and Fast MSO1

DOI10.1007/978-3-642-32589-2_38zbMath1365.68323OpenAlexW22683998MaRDI QIDQ2912741

Robert Ganian, Reshma Ramadurai, Patrice Ossona de Mendez, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek

Publication date: 25 September 2012

Published in: Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-32589-2_38

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Structural characterization of families of graphs (05C75)

Related Items

Tree-depth and vertex-minors, Between treewidth and clique-width, Between Treewidth and Clique-Width, Graphs of bounded depth‐2 rank‐brittleness, On low tree-depth decompositions, A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth, Unnamed Item, Extended MSO model checking via small vertex integrity, Polynomial graph invariants from homomorphism numbers, Regular partitions of gentle graphs, Practical algorithms for MSO model-checking on tree-decomposable graphs, Classes of graphs with low complexity: the case of classes with bounded linear rankwidth, Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity, Limits of structures and the example of tree semi-lattices, Parameterized shifted combinatorial optimization, On low rank-width colorings, Obstructions for bounded shrub-depth and rank-depth, Unnamed Item, Efficient parallel algorithms for parameterized problems, Unnamed Item