From tree-decompositions to clique-width terms

DOI10.1016/j.dam.2017.04.040zbMath1395.05097OpenAlexW2617926292MaRDI QIDQ2413974

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

planar graphclique-widthtree-widthincidence graphsparse graphfixed-parameter tractable algorithm

Mathematics Subject Classification ID

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

Related Items

Grammars and clique-width bounds from split decompositions ⋮ On quasi-planar graphs: clique-width and logical description ⋮ Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs ⋮ How to compute digraph width measures on directed co-graphs ⋮ Unnamed Item ⋮ Comparing linear width parameters for directed graphs

Uses Software

• ComputeTW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
• Characterizing width two for variants of treewidth
• Fundamentals of parameterized complexity
• On the model-checking of monadic second-order formulas with edge set quantifications
• Rank-width and tree-width of \(H\)-minor-free graphs
• Boolean-width of graphs
• Treewidth computations. I: Upper bounds
• On tree-partition-width
• A partial k-arboretum of graphs with bounded treewidth
• Conjunctive-query containment and constraint satisfaction
• Automata for the verification of monadic second-order graph properties
• Linear time solvable optimization problems on graphs of bounded clique-width
• A characterisation of clique-width through nested partitions
• Counting truth assignments of formulas of bounded tree-width or clique-width
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Model-Checking by Infinite Fly-Automata
• Fixed-Parameter Tractability and Characterizations of Small Special Treewidth
• Clique-Width is NP-Complete
• Complexity of Finding Embeddings in a k-Tree
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• On the Relationship Between Clique-Width and Treewidth
• Rank‐width is less than or equal to branch‐width
• Graph-Theoretic Concepts in Computer Science
• Computations by fly-automata beyond monadic second-order logic