ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
From MaRDI portal
Publication:5249049
DOI10.1142/S0129054100000260zbMath1320.05090MaRDI QIDQ5249049
Martin Charles Golumbic, Udi Rotics
Publication date: 29 April 2015
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
05C75: Structural characterization of families of graphs
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, Clique-width of path powers, Finding clubs in graph classes, 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, A note on connected dominating sets of distance-hereditary graphs, On factorial properties of chordal bipartite graphs, The complexity of finding uniform sparsest cuts in various graph classes, Clique-width with an inactive label, Practical algorithms for MSO model-checking on tree-decomposable graphs, Dominating induced matchings for \(P_7\)-free graphs in linear time, The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs, A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs, The behavior of clique-width under graph operations and graph transformations, Boundary properties of graphs for algorithmic graph problems, Algorithmic uses of the Feferman-Vaught theorem, Minimal classes of graphs of unbounded clique-width, The carving-width of generalized hypercubes, On distance-3 matchings and induced matchings, On the complexity of the dominating induced matching problem in hereditary classes of graphs, Boolean-width of graphs, Compact representation of graphs of small clique-width, Solving problems on generalized convex graphs via mim-width, Vertex-minors, monadic second-order logic, and a conjecture by Seese, Graph classes with and without powers of bounded clique-width, Graph parameters measuring neighbourhoods in graphs-bounds and applications, Circle graphs and monadic second-order logic, Rooted directed path graphs are leaf powers, Recent developments on graphs of bounded clique-width, Clique-width of graphs defined by one-vertex extensions, The NLC-width and clique-width for powers of graphs of bounded tree-width, Independent domination in finitely defined classes of graphs, Tree-width and the monadic quantifier hierarchy., Stability number of bull- and chair-free graphs revisited, (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization., Induced minor free graphs: isomorphism and clique-width, Simple linear-time algorithms for counting independent sets in distance-hereditary graphs, Graphs vertex-partitionable into strong cliques, Dynamic monopolies for interval graphs with bounded thresholds, Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width, On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph, Chordal bipartite graphs of bounded tree- and clique-width, Edge dominating set and colorings on graphs with fixed clique-width, Automata for the verification of monadic second-order graph properties, Split permutation graphs, Cluster deletion on interval graphs and split related graphs, On the maximum cardinality cut problem in proper interval graphs and related graph classes, \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited, Optimal centrality computations within bounded clique-width graphs, Maximum matching in almost linear time on graphs of bounded clique-width, Uncountably many minimal hereditary classes of graphs of unbounded clique-width, A polynomial-time approximation to a minimum dominating set in a graph, Grammars and clique-width bounds from split decompositions, Between clique-width and linear clique-width of bipartite graphs, On strict (outer-)confluent graphs, The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond, Mim-width. II. The feedback vertex set problem, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, Comparing linear width parameters for directed graphs, Clique-width of full bubble model graphs, 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), Rank-width: algorithmic and structural results, On the thinness and proper thinness of a graph, Bounding clique-width via perfect graphs, Faster algorithms for vertex partitioning problems parameterized by clique-width, Finding a minimum path cover of a distance-hereditary graph in polynomial time, Line graphs of bounded clique-width, Solving \#SAT using vertex covers, NP-hard graph problems and boundary classes of graphs, Equistable distance-hereditary graphs, Counting truth assignments of formulas of bounded tree-width or clique-width, Distance-hereditary graphs are clique-perfect, Vertex disjoint paths on clique-width bounded graphs, Rank-width and vertex-minors, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Rebuilding convex sets in graphs, On the relationship between NLC-width and linear NLC-width, Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs, On the computational complexity of the bipartizing matching problem, Computing densest \(k\)-subgraph with structural parameters, Domination and convexity problems in the target set selection model, Bounding Clique-Width via Perfect Graphs, Open Problems on Graph Coloring for Special Graph Classes, A new representation of proper interval graphs with an application to clique-width, Bounding the Clique-Width of H-free Chordal Graphs, A SAT Approach to Clique-Width, Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width, Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width, Unnamed Item, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES, The complexity of the matching-cut problem for planar graphs and other graph classes, Dominating Induced Matchings, On Distance-3 Matchings and Induced Matchings, Unnamed Item, Unnamed Item, Unnamed Item, On Strict (Outer-)Confluent Graphs, On spectra of sentences of monadic second order logic with counting, Linear Recurrence Relations for Graph Polynomials, Ptolemaic Graphs and Interval Graphs Are Leaf Powers, GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH, Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs, Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs, Bounding the clique-width of \(H\)-free split graphs, On efficient domination for some classes of \(H\)-free chordal graphs, On efficient domination for some classes of \(H\)-free chordal graphs, Graph functionality, Node multiway cut and subset feedback vertex set on graphs of bounded mim-width, Solving problems on generalized convex graphs via mim-width, Coloring rings, A class of graphs with large rankwidth, Twin-distance-hereditary digraphs, Some new algorithmic results on co-secure domination in graphs
Cites Work
- Completely separable graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Handle-rewriting hypergraph grammars
- Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Restricted unimodular chordal graphs
- A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
- ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
