Upper bounds to the clique width of graphs

From MaRDI portal

Publication:1975365

Jump to:navigation, search

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

Bruno Courcelle, 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

algorithms monadic second-order logic tree decomposition modular decomposition hierarchical 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

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, On structural parameterizations of load coloring, Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs, Rainbow independent sets on dense graph classes, Structural parameterizations of clique coloring, Solving problems on generalized convex graphs via mim-width, Parameterized model checking of rendezvous systems, Mock threshold graphs, Collective tree spanners in graphs with bounded parameters, Model counting for CNF formulas of bounded modular treewidth, The VC-dimension of graphs with respect to \(k\)-connected subgraphs, Reasoning about integrity constraints for tree-structured data, Vertex-minors, monadic second-order logic, and a conjecture by Seese, A local characterization of bounded clique-width for line graphs, Characterizations for restricted graphs of NLC-width 2, Algorithmic uses of the Feferman-Vaught theorem, Satisfiability of acyclic and almost acyclic CNF formulas, Tight complexity bounds for FPT subgraph problems parameterized by the clique-width, \(H\)-product of graphs, \(H\)-threshold graphs and threshold-width of graphs, Colouring of graphs with Ramsey-type forbidden subgraphs, Structure and algorithms for (cap, even hole)-free graphs, Are there any good digraph width measures?, Graph classes with and without powers of bounded clique-width, Independent domination in finitely defined classes of graphs, The most vital nodes with respect to independent set and vertex cover, A monadic second-order definition of the structure of convex hypergraphs., Tree-width and the monadic quantifier hierarchy., 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, Compact labelings for efficient first-order model-checking, On switching classes, NLC-width, cliquewidth and treewidth, On variations of \(P_{4}\)-sparse graphs, Stability number of bull- and chair-free graphs revisited, Query efficient implementation of graphs of bounded clique-width, Directed NLC-width, Classifying the clique-width of \(H\)-free bipartite graphs, Polynomial graph invariants from homomorphism numbers, Induced minor free graphs: isomorphism and clique-width, Fast evaluation of interlace polynomials on graphs of bounded treewidth, On the structure and stability number of \(P_{5}\)- and co-chair-free graphs, New plain-exponential time classes for graph homomorphism, On factorial properties of chordal bipartite graphs, Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis, The complexity of finding uniform sparsest cuts in various graph classes, Clique-width of countable graphs: A compactness property., Clique-width of partner-limited graphs, The enumeration of vertex induced subgraphs with respect to the number of components, On prime inductive classes of graphs, Clique-width with an inactive label, (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization., Practical algorithms for MSO model-checking on tree-decomposable graphs, Digraph measures: Kelly decompositions, games, and orderings, Minimal classes of graphs of unbounded clique-width, Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs, The coloring problem for classes with two small obstructions, Polynomial-time algorithms for energy games with special weight structures, On the parameterized complexity of computing balanced partitions in graphs, Circle graphs and monadic second-order logic, Computing the clique-width of cactus graphs, Solving some NP-complete problems using split decomposition, Well-quasi-ordering versus clique-width, A new graph construction of unbounded clique-width, The behavior of clique-width under graph operations and graph transformations, Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm, Block-graph width, Recent developments on graphs of bounded clique-width, Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width, Logical aspects of Cayley-graphs: the group case, Rank-width and tree-width of \(H\)-minor-free graphs, Finding vertex-surjective graph homomorphisms, On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth, Graphs of linear clique-width at most 3, On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph, Upper domination: towards a dichotomy through boundary properties, Well-quasi-ordering versus clique-width: new results on bigenic classes, Compact representation of graphs of small clique-width, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, Efficient algorithms for Roman domination on some classes of graphs, Structure and stability number of chair-, co-P- and gem-free graphs revisited, Recurrence relations for graph polynomials on bi-iterative families of graphs, Efficient algorithms for network localization using cores of underlying graphs, On the OBDD size for graphs of bounded tree- and clique-width, The NLC-width and clique-width for powers of graphs of bounded tree-width, Graph operations characterizing rank-width, Colouring vertices of triangle-free graphs without forests, Chordal bipartite graphs of bounded tree- and clique-width, An extension of the bivariate chromatic polynomial, Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time., Edge dominating set and colorings on graphs with fixed clique-width, The evaluation of first-order substitution is monadic second-order compatible, 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, Connection Matrices for MSOL-Definable Structural Invariants, 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, Uncountably many minimal hereditary classes of graphs of unbounded clique-width, Algorithms for vertex-partitioning problems on graphs with fixed clique-width., Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs, Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width, Rank-width of random graphs, Polynomial algorithms for protein similarity search for restricted mRNA structures, Complexity of Ising Polynomials, On powers of graphs of bounded NLC-width (clique-width), Directed width parameters on semicomplete digraphs, The relative clique-width of a graph, On the structure of graphs without claw, \(4K_1\) and co-R, The rank-width of edge-coloured graphs, Boundary classes for graph problems involving non-local properties, Distance from triviality 2.0: hybrid parameterizations, Rank-width: algorithmic and structural results, Characterizations of \((4 K_1,C_4,C_5)\)-free graphs, 4-coloring \((P_6, \text{bull})\)-free graphs, From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats, Computing the largest bond and the maximum connected cut of a graph, On compiling structured CNFs to OBDDs, Subgraph complementation, Parameterized complexity of distance labeling and uniform channel assignment problems, Infinitely many minimal classes of graphs of unbounded clique-width, Bounding the Clique-Width of H-free Chordal Graphs, A SAT Approach to Clique-Width, On the thinness and proper thinness of a graph, Fast exact algorithms for some connectivity problems parameterized by clique-width, Computing densest \(k\)-subgraph with structural parameters, Parameterized complexity of envy-free resource allocation in social networks, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, Long induced paths in minor-closed graph classes and beyond, On the clique-width of \(( 4 K_1 , C_4 , C_5 , C_7 )\)-free graphs, FPT and kernelization algorithms for the induced tree problem, Automata for the verification of monadic second-order graph properties, On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs, Perfectly matched sets in graphs: parameterized and exact computation, On strict (outer-)confluent graphs, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, Linear Clique‐Width for Hereditary Classes of Cographs, Obstructions for linear rank-width at most 1, Digraph width measures in parameterized algorithmics, Constrained-path labellings on graphs of bounded clique-width, Solutions for subset sum problems with special digraph constraints, Latency-bounded target set selection in social networks, Faster algorithms for vertex partitioning problems parameterized by clique-width, How to compute digraph width measures on directed co-graphs, The average cut-rank of graphs, Classes of graphs with low complexity: the case of classes with bounded linear rankwidth, Finding a minimum path cover of a distance-hereditary graph in polynomial time, Vertex-minor reductions can simulate edge contractions, Upper bounds to the clique width of graphs, Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs, Line graphs of bounded clique-width, Efficient computation of the oriented chromatic number of recursively defined digraphs, Solving \#SAT using vertex covers, Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width, Satisfiability of Acyclic and almost Acyclic CNF Formulas (II), Polynomial-time algorithm for isomorphism of graphs with clique-width at most three, Low-congestion shortcut and graph parameters, Counting truth assignments of formulas of bounded tree-width or clique-width, Oriented coloring on recursively defined digraphs, Distance-hereditary graphs are clique-perfect, Branch-width, parse trees, and monadic second-order logic for matroids., The monadic second-order logic of graphs. XV: On a conjecture by D. Seese, Approximating clique-width and branch-width, Recognizability, hypergraph operations, and logical types, On characterizations for subclasses of directed co-graphs, Linear layouts measuring neighbourhoods in graphs, Vertex disjoint paths on clique-width bounded graphs, A model-theoretic characterisation of clique width, Vector domination in split-indifference graphs, Alliances in graphs of bounded clique-width, Obstructions for bounded shrub-depth and rank-depth, Measuring what matters: a hybrid approach to dynamic programming with treewidth, The intersection of two vertex coloring problems, Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, Using decomposition-parameters for QBF: mind the prefix!, A Boundary Property for Upper Domination, Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes, Independent Set Reconfiguration in Cographs and their Generalizations, Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width, Structurally parameterized \(d\)-scattered set, \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited, A new representation of proper interval graphs with an application to clique-width, Comparing linear width parameters for directed graphs, Colouring square-free graphs without long induced paths, Rank-width and vertex-minors, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, The recognizability of sets of graphs is a robust property, Revising Johnson's table for the 21st century, Maximum matching in almost linear time on graphs of bounded clique-width, On the relationship between NLC-width and linear NLC-width, Clique-width of full bubble model graphs, Linear rank-width and linear clique-width of trees, A characterisation of clique-width through nested partitions, Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT, Clique-width and edge contraction, Knocking out \(P_k\)-free graphs, Conflict-free coloring: graphs of bounded clique width and intersection graphs

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1975365&oldid=14436167"