Upper bounds to the clique width of graphs

DOI10.1016/S0166-218X(99)00184-5zbMath0958.05105OpenAlexW1993328543WikidataQ56475000 ScholiaQ56475000MaRDI QIDQ1975365

Stephan Olariu

Publication date: 30 March 2001

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00184-5

zbMATH Keywords

algorithmsmonadic second-order logictree decompositionmodular decompositionhierarchical graph decomposition

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (only showing first 100 items - show all)

Simple monadic theories and partition width ⋮ Computing L(p,1)-Labeling with Combined Parameters ⋮ Containment of Monadic Datalog Programs via Bounded Clique-Width ⋮ A Most General Edge Elimination Polynomial ⋮ Evaluations of Graph Polynomials ⋮ On spectra of sentences of monadic second order logic with counting ⋮ On Compiling Structured CNFs to OBDDs ⋮ Inductive computations on graphs defined by clique-width expressions ⋮ On Strict (Outer-)Confluent Graphs ⋮ Colouring square-free graphs without long induced paths. ⋮ Unnamed Item ⋮ The Smallest Classes of Binary and Ternary Matroids Closed under Direct Sums and Complements ⋮ On the minimum cycle cover problem on graphs with bounded co-degeneracy ⋮ Graphs of bounded depth‐2 rank‐brittleness ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ Graphs of Linear Clique-Width at Most 3 ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels ⋮ Tangle bases: Revisited ⋮ On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract) ⋮ Efficient First-Order Model-Checking Using Short Labels ⋮ On structural parameterizations of star coloring ⋮ Twin-distance-hereditary digraphs ⋮ Tree-Width and Optimization in Bounded Degree Graphs ⋮ Graph Operations Characterizing Rank-Width and Balanced Graph Expressions ⋮ The Clique-Width of Tree-Power and Leaf-Power Graphs ⋮ Dominator coloring and CD coloring in almost cluster graphs ⋮ Critical properties of bipartite permutation graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ Monoidal Width: Capturing Rank Width ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Unnamed Item ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Boundary Classes of Planar Graphs ⋮ Some new algorithmic results on co-secure domination in graphs ⋮ Locating Eigenvalues of Symmetric Matrices - A Survey ⋮ Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs ⋮ On the structure of (pan, even hole)‐free graphs ⋮ Unnamed Item ⋮ Parameterized Complexity of Safe Set ⋮ THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Compact and localized distributed data structures ⋮ GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH ⋮ Model checking existential logic on partially ordered sets ⋮ Solving problems on generalized convex graphs via mim-width ⋮ On structural parameterizations of load coloring ⋮ Fifty years of the spectrum problem: survey and new results ⋮ Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width ⋮ $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ Parameterized algorithms for the happy set problem ⋮ GETGRATS ⋮ Graph Operations, Graph Transformations and Monadic Second-Order Logic: ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Structural Parameterizations of the Harmless Set Problem ⋮ Connection Matrices for MSOL-Definable Structural Invariants ⋮ Vertex-minors of graphs: a survey ⋮ Succinct data structures for bounded clique-width graphs ⋮ Parameterized aspects of triangle enumeration ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Are There Any Good Digraph Width Measures? ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes ⋮ Excluding a bipartite circle graph from line graphs ⋮ Linear Recurrence Relations for Graph Polynomials ⋮ An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem ⋮ A polynomial kernel for distance-hereditary vertex deletion ⋮ Unnamed Item ⋮ Graph functionality ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Enumeration of Minimal Dominating Sets and Variants ⋮ New Plain-Exponential Time Classes for Graph Homomorphism ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Partial complementation of graphs ⋮ ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Finding Branch-Decompositions of Matroids, Hypergraphs, and More ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width ⋮ Unnamed Item ⋮ Tree Pivot-Minors and Linear Rank-Width ⋮ Canonisation and Definability for Graphs of Bounded Rank Width ⋮ Clique-width of path powers ⋮ Characterizations for co-graphs defined by restricted NLC-width or clique-width operations ⋮ Trees, grids, and MSO decidability: from graphs to matroids ⋮ The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions. ⋮ Tree-depth and vertex-minors ⋮ Eigenvalue location in graphs of small clique-width ⋮ Acyclic coloring parameterized by directed clique-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monadic second-order evaluations on tree-decomposable graphs
• The structure of the models of decidable monadic theories of graphs
• Graph minors. V. Excluding a planar graph
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• \(k\)-NLC graphs and polynomial algorithms
• The monadic second-order logic of graphs. X: Linear orderings
• The monadic second-order logic of graphs. VIII: Orientations
• Structural properties of context-free sets of graphs generated by vertex replacement
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• A Linear Recognition Algorithm for Cographs
• Incremental modular decomposition
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• An algebraic theory of graph reduction
• Handbook of Graph Grammars and Computing by Graph Transformation

This page was built for publication: Upper bounds to the clique width of graphs