Branch-width, parse trees, and monadic second-order logic for matroids.
From MaRDI portal
Publication:2490835
DOI10.1016/J.JCTB.2005.08.005zbMATH Open1088.05022OpenAlexW1980469100MaRDI QIDQ2490835FDOQ2490835
Authors: 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
Recommendations
- scientific article; zbMATH DE number 1962824
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- scientific article; zbMATH DE number 1086493
- Monadic second-order logic on tree-like structures
- Monadic second order logic on tree-like structures
- The monadic second-order logic of graphs, II: Infinite graphs of bounded width
- Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications
- Monadic second order finite satisfiability and unbounded tree-width
- Monadic Second-Order Logic and Transitive Closure Logics over Trees
Combinatorics in computer science (68R05) Automata and formal grammars in connection with logical questions (03D05) Combinatorial aspects of matroids and geometric lattices (05B35)
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Constructive linear time algorithms for branchwidth
- 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\)
- Title not available (Why is that?)
- The structure of the models of decidable monadic theories of graphs
- Branch-width and well-quasi-ordering in matroids and graphs.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Mathematical Foundations of Computer Science 2003
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- Parameterized and Exact Computation
Cited In (26)
- Trees, grids, and MSO decidability: from graphs to matroids
- Title not available (Why is that?)
- Decomposition width of matroids
- Monadic second-order model-checking on decomposable matroids
- Fast FPT-approximation of branchwidth
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Tree automata and pigeonhole classes of matroids. II
- Directed Nowhere Dense Classes of Graphs
- Myhill-Nerode Methods for Hypergraphs
- Parameterized Leaf Power Recognition via Embedding into Graph Products
- Tree automata and pigeonhole classes of matroids. I
- Parameterized and Exact Computation
- First order convergence of matroids
- Branch-depth: generalizing tree-depth of graphs
- Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
- Confronting intractability via parameters
- Finding branch-decompositions of matroids, hypergraphs, and more
- Finding Branch-Decompositions of Matroids, Hypergraphs, and More
- Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
- Covering Vectors by Spaces: Regular Matroids
- Matroid tree-width
- Parameterized leaf power recognition via embedding into graph products
- A Simpler Self-reduction Algorithm for Matroid Path-Width
- The rank-width of edge-coloured graphs
This page was built for publication: Branch-width, parse trees, and monadic second-order logic for matroids.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2490835)
