Branch-width, parse trees, and monadic second-order logic for matroids.

DOI10.1016/j.jctb.2005.08.005zbMath1088.05022OpenAlexW1980469100MaRDI QIDQ2490835

Petr Hliněný

Publication date: 18 May 2006

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2005.08.005

zbMATH Keywords

fixed-parameter complexitytree automatonmatroid representation

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Automata and formal grammars in connection with logical questions (03D05) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

Tree automata and pigeonhole classes of matroids. I, Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids, First order convergence of matroids, Matroid tree-width, Covering Vectors by Spaces: Regular Matroids, Vertex-minors, monadic second-order logic, and a conjecture by Seese, The rank-width of edge-coloured graphs, A Simpler Self-reduction Algorithm for Matroid Path-Width, Finding branch-decompositions of matroids, hypergraphs, and more, Decomposition width of matroids, Tree automata and pigeonhole classes of matroids. II, Confronting intractability via parameters, Branch-depth: generalizing tree-depth of graphs, Parameterized Leaf Power Recognition via Embedding into Graph Products, On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width, Monadic second-order model-checking on decomposable matroids, Parameterized leaf power recognition via embedding into graph products, Finding Branch-Decompositions of Matroids, Hypergraphs, and More, Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming, Myhill-Nerode Methods for Hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The structure of the models of decidable monadic theories of graphs
• Graph minors. X: Obstructions to tree-decomposition
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• On the excluded minors for the matroids of branch-width \(k\)
• Branch-width and well-quasi-ordering in matroids and graphs.
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Approximating clique-width and branch-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Constructive linear time algorithms for branchwidth
• Parameterized and Exact Computation
• Mathematical Foundations of Computer Science 2003
• Graph-Theoretic Concepts in Computer Science