Multi-clique-width

DOI10.4230/LIPICS.ITCS.2017.14MaRDI QIDQ4638063zbMATH OpenFDO

Authors Martin Fürer

Publication date 3 May 2018

Full work available at URL https://arxiv.org/abs/1511.04479

zbMATH Keywords

graph coloringclique-widthparameterized complexitytree-widthindependent set polynomial

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Polynomial-time recognition of clique-width 3 graphs
• The relative clique-width of a graph
• Clique-width: on the price of generality
• Multicut on graphs of bounded clique-width
• Computing Graph Polynomials on Graphs of Bounded Clique-Width

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
• A c^k n 5-approximation algorithm for treewidth
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Approximating clique-width and branch-width
• Approximating rank-width and clique-width quickly
• Between treewidth and clique-width
• Boolean-width of graphs
• Clique-width minimization is NP-hard
• Complexity of Finding Embeddings in a k-Tree
• Constrained-path labellings on graphs of bounded clique-width
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Finding Branch-Decompositions and Rank-Decompositions
• Fundamentals of parameterized complexity
• Fusion in relational structures and the verification of monadic second-order properties
• Graph minors. III. Planar tree-width
• Handle-rewriting hypergraph grammars
• Linear time solvable optimization problems on graphs of bounded clique-width
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• On the Relationship Between Clique-Width and Treewidth
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Upper bounds to the clique width of graphs

Cited in

(3)

• Efficient diagonalization of symmetric matrices associated with graphs of small treewidth
• Space-efficient parameterized algorithms on graphs of low shrubdepth
• The parameterized complexity of learning monadic second-order logic

This page was built for publication: Multi-clique-width

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