From tree-decompositions to clique-width terms

DOI10.1016/J.DAM.2017.04.040MaRDI QIDQ2413974zbMATH OpenOpenAlexFDO

Authors Bruno Courcelle

Publication date 17 September 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2017.04.040

zbMATH Keywords

clique-widthfixed-parameter tractable algorithmincidence graphplanar graphsparse graphtree-width

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Density (toughness, etc.) (05C42) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• On the Relationship Between Clique-Width and Treewidth
• The relative clique-width of a graph
• scientific article; zbMATH DE number 2044924
• scientific article; zbMATH DE number 1696534
• Linear time solvable optimization problems on graphs of bounded clique-width

Cites work

• A c^k n 5-approximation algorithm for treewidth
• A characterisation of clique-width through nested partitions
• A partial k-arboretum of graphs with bounded treewidth
• Automata for the verification of monadic second-order graph properties
• Boolean-width of graphs
• Characterizing width two for variants of treewidth
• Clique-width is NP-complete
• Complexity of Finding Embeddings in a k-Tree
• Computations by fly-automata beyond monadic second-order logic
• Conjunctive-query containment and constraint satisfaction
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• Fixed-parameter tractability and characterizations of small special treewidth
• Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
• Fundamentals of parameterized complexity
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 1696534 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 5032352 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Model-checking by infinite fly-automata
• On the model-checking of monadic second-order formulas with edge set quantifications
• On the Relationship Between Clique-Width and Treewidth
• On tree-partition-width
• Rank-width and tree-width of \(H\)-minor-free graphs
• Rank‐width is less than or equal to branch‐width
• Treewidth computations. I: Upper bounds

Cited in

(16)

• Tree-width, clique-minors, and eigenvalues.
• Grammars and clique-width bounds from split decompositions
• On quasi-planar graphs: clique-width and logical description
• How to compute digraph width measures on directed co-graphs
• Comparing linear width parameters for directed graphs
• A model-theoretic characterisation of clique width
• The relative clique-width of a graph
• scientific article; zbMATH DE number 1696534 (Why is no real title available?)
• Organizing the atoms of the clique separator decomposition into an atom tree
• scientific article; zbMATH DE number 2044924 (Why is no real title available?)
• scientific article; zbMATH DE number 7559449 (Why is no real title available?)
• On the Relationship Between Clique-Width and Treewidth
• Inductive computations on graphs defined by clique-width expressions
• Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
• Spined categories: generalizing tree-width beyond graphs
• MSO undecidability for hereditary classes of unbounded clique-width

Describes a project that uses

Uses Software

• ComputeTW

This page was built for publication: From tree-decompositions to clique-width terms

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