On the Relationship Between Clique-Width and Treewidth

DOI10.1137/S0097539701385351zbMath1069.05067OpenAlexW2087911394MaRDI QIDQ5317177

Publication date: 16 September 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539701385351

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (84)

Vertex cover meets scheduling ⋮ Eigenvalue location in graphs of small clique-width ⋮ Acyclic coloring parameterized by directed clique-width ⋮ (Total) vector domination for graphs with bounded branchwidth ⋮ Parameterized Complexity of Geodetic Set ⋮ Between treewidth and clique-width ⋮ Polynomial algorithms for protein similarity search for restricted mRNA structures ⋮ On powers of graphs of bounded NLC-width (clique-width) ⋮ Parameterized complexity of graph burning ⋮ Subexponential Fixed-Parameter Algorithms for Partial Vector Domination ⋮ Rank-width: algorithmic and structural results ⋮ On quasi-planar graphs: clique-width and logical description ⋮ MSOL partitioning problems on graphs of bounded treewidth and clique-width ⋮ Between Treewidth and Clique-Width ⋮ Parameterized complexity of distance labeling and uniform channel assignment problems ⋮ Parameterized edge Hamiltonicity ⋮ From tree-decompositions to clique-width terms ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ A SAT Approach to Clique-Width ⋮ On the minimum cycle cover problem on graphs with bounded co-degeneracy ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Clique‐width: Harnessing the power of atoms ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels ⋮ On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract) ⋮ Graph classes with and without powers of bounded clique-width ⋮ Bounding clique-width via perfect graphs ⋮ Graphs of separability at most 2 ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ On the model-checking of monadic second-order formulas with edge set quantifications ⋮ Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs ⋮ The Clique-Width of Tree-Power and Leaf-Power Graphs ⋮ The Treewidth and Pathwidth of Graph Unions ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Unnamed Item ⋮ On the structure of (pan, even hole)‐free graphs ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Linear Clique‐Width for Hereditary Classes of Cographs ⋮ Dominating induced matchings in graphs without a skew star ⋮ Latency-bounded target set selection in social networks ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ The Effect of Planarization on Width ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Vertex-minor reductions can simulate edge contractions ⋮ Graphs of Separability at Most Two: Structural Characterizations and Their Consequences ⋮ Line graphs of bounded clique-width ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width ⋮ Circle graphs and monadic second-order logic ⋮ Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width ⋮ Low-congestion shortcut and graph parameters ⋮ Parameterized Complexity of Graph Burning ⋮ Subexponential fixed-parameter algorithms for partial vector domination ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Recent developments on graphs of bounded clique-width ⋮ On the approximate compressibility of connected vertex cover ⋮ \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth ⋮ On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width ⋮ Rank-width and tree-width of \(H\)-minor-free graphs ⋮ Approximating clique-width and branch-width ⋮ On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth ⋮ Boolean-width of graphs ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ Compact representation of graphs of small clique-width ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ Alliances in graphs of bounded clique-width ⋮ The Effect of Planarization on Width ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ The NLC-width and clique-width for powers of graphs of bounded tree-width ⋮ Graph operations characterizing rank-width ⋮ A new representation of proper interval graphs with an application to clique-width ⋮ Boolean-Width of Graphs ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ Unnamed Item ⋮ Parameterized Complexity of Geodetic Set ⋮ Regular independent sets

This page was built for publication: On the Relationship Between Clique-Width and Treewidth