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
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
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph minors. X: Obstructions to tree-decomposition
- 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
- 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\)
- The structure of the models of decidable monadic theories of graphs
- Branch-width and well-quasi-ordering in matroids and graphs.
- Mathematical Foundations of Computer Science 2003
- Graph-Theoretic Concepts in Computer Science
- Parameterized and Exact Computation
Cited In (23)
- 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
- 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
Recommendations
- Title not available (Why is that?) π π
- Title not available (Why is that?) π π
- Monadic second-order logic on tree-like structures π π
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues π π
- The monadic second-order logic of graphs, II: Infinite graphs of bounded width π π
- Monadic Second Order Finite Satisfiability and Unbounded Tree-Width π π
- Monadic second order logic on tree-like structures π π
- Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications π π
- Monadic Second-Order Logic and Transitive Closure Logics over Trees π π
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)
