Upper bounds to the clique width of graphs
From MaRDI portal
The authors bound the clique width of a graph in terms of its tree width and also in terms of the clique width of its edge complement.
Cites work
- \(k\)-NLC graphs and polynomial algorithms
- A Linear Recognition Algorithm for Cographs
- An algebraic theory of graph reduction
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- Easy problems for tree-decomposable graphs
- Graph minors. V. Excluding a planar graph
- Handbook of Graph Grammars and Computing by Graph Transformation
- Handle-rewriting hypergraph grammars
- scientific article; zbMATH DE number 177441 (Why is no real title available?)
- scientific article; zbMATH DE number 1142299 (Why is no real title available?)
- scientific article; zbMATH DE number 809155 (Why is no real title available?)
- scientific article; zbMATH DE number 1456953 (Why is no real title available?)
- Incremental modular decomposition
- Monadic second-order evaluations on tree-decomposable graphs
- Structural properties of context-free sets of graphs generated by vertex replacement
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The monadic second-order logic of graphs. VII: Graphs as relational structures
- The monadic second-order logic of graphs. VIII: Orientations
- The monadic second-order logic of graphs. X: Linear orderings
- The structure of the models of decidable monadic theories of graphs
- Upper bounds to the clique width of graphs
Cited in
(only showing first 100 items - show all)- Efficient algorithms for Roman domination on some classes of graphs
- Structure and stability number of chair-, co-P- and gem-free graphs revisited
- 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
- An extension of the bivariate chromatic polynomial
- Independent domination in finitely defined classes of graphs
- A monadic second-order definition of the structure of convex hypergraphs.
- Tree-width and the monadic quantifier hierarchy.
- 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
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- Clique-width of countable graphs: A compactness property.
- Clique-width of partner-limited graphs
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- The evaluation of first-order substitution is monadic second-order compatible
- Eigenvalue location in graphs of small clique-width
- Parameterized model checking of rendezvous systems
- Mock threshold graphs
- Reasoning about integrity constraints for tree-structured data
- Structure and algorithms for (cap, even hole)-free graphs
- Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
- Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
- Computing the clique-width of cactus graphs
- Well-quasi-ordering versus 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 the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- Chordal bipartite graphs of bounded tree- and clique-width
- 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 monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Automata for the verification of monadic second-order graph properties
- Constrained-path labellings on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Oriented coloring on recursively defined digraphs
- On characterizations for subclasses of directed co-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
- Structurally parameterized \(d\)-scattered set
- \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- Revising Johnson's table for the 21st century
- Maximum matching in almost linear time on graphs of bounded clique-width
- Tractability beyond -acyclicity for conjunctive queries with negation and SAT
- Conflict-free coloring: graphs of bounded clique width and intersection graphs
- Uncountably many minimal hereditary classes of graphs of unbounded clique-width
- Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs
- Directed width parameters on semicomplete digraphs
- On the structure of graphs without claw, \(4K_1\) and co-R
- Distance from triviality 2.0: hybrid parameterizations
- From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
- Subgraph complementation
- On the clique-width of ( 4 K₁ , C₄ , C₅ , C₇ )-free graphs
- On strict (outer-)confluent graphs
- Solutions for subset sum problems with special digraph constraints
- 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
- Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- Low-congestion shortcut and graph parameters
- Vector domination in split-indifference graphs
- The intersection of two vertex coloring 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!
- Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
- Comparing linear width parameters for directed graphs
- Colouring square-free graphs without long induced paths
- Clique-width of full bubble model graphs
- Linear rank-width and linear clique-width of trees
- A characterisation of clique-width through nested partitions
- Clique-width and edge contraction
- Knocking out \(P_k\)-free graphs
- Polynomial algorithms for protein similarity search for restricted mRNA structures
- On powers of graphs of bounded NLC-width (clique-width)
- The rank-width of edge-coloured graphs
- Boundary classes for graph problems involving non-local properties
- 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
- On compiling structured CNFs to OBDDs
- Parameterized complexity of distance labeling and uniform channel assignment problems
- Infinitely many minimal classes of graphs of unbounded clique-width
- On the thinness and proper thinness of a graph
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Obstructions for linear rank-width at most 1
- Digraph width measures in parameterized algorithmics
- Latency-bounded target set selection in social networks
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- Vertex-minor reductions can simulate edge contractions
- Line graphs of bounded clique-width
- Solving \#SAT using vertex covers
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Distance-hereditary graphs are clique-perfect
This page was built for publication: Upper bounds to the clique width of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1975365)
