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)
Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (only showing first 100 items - show all)
On spectra of sentences of monadic second order logic with counting ⋮ On Strict (Outer-)Confluent Graphs ⋮ Coloring rings ⋮ A class of graphs with large rankwidth ⋮ Twin-distance-hereditary digraphs ⋮ Some new algorithmic results on co-secure domination in graphs ⋮ GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Unnamed Item ⋮ Linear Recurrence Relations for Graph Polynomials ⋮ Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Ptolemaic Graphs and Interval Graphs Are Leaf Powers ⋮ 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 ⋮ Clique-width of path powers ⋮ Uncountably many minimal hereditary classes of graphs of unbounded clique-width ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Unnamed Item ⋮ Polynomial algorithms for protein similarity search for restricted mRNA structures ⋮ On powers of graphs of bounded NLC-width (clique-width) ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Rank-width: algorithmic and structural results ⋮ Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs ⋮ Grammars and clique-width bounds from split decompositions ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ A SAT Approach to Clique-Width ⋮ On the thinness and proper thinness of a graph ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Between clique-width and linear clique-width of bipartite graphs ⋮ On the computational complexity of the bipartizing matching problem ⋮ Finding clubs in graph classes ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ Graph classes with and without powers of bounded clique-width ⋮ Independent domination in finitely defined classes of graphs ⋮ Bounding clique-width via perfect graphs ⋮ 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 ⋮ A note on connected dominating sets of distance-hereditary graphs ⋮ Domination and convexity problems in the target set selection model ⋮ Stability number of bull- and chair-free graphs revisited ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ Automata for the verification of monadic second-order graph properties ⋮ Simple linear-time algorithms for counting independent sets in distance-hereditary graphs ⋮ On strict (outer-)confluent graphs ⋮ On factorial properties of chordal bipartite graphs ⋮ Graphs vertex-partitionable into strong cliques ⋮ THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ 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 ⋮ Dominating induced matchings for \(P_7\)-free graphs in linear time ⋮ Minimal classes of graphs of unbounded clique-width ⋮ The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs ⋮ Finding a minimum path cover of a distance-hereditary graph in polynomial time ⋮ Line graphs of bounded clique-width ⋮ The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond ⋮ Solving \#SAT using vertex covers ⋮ Dynamic monopolies for interval graphs with bounded thresholds ⋮ Graph parameters measuring neighbourhoods in graphs-bounds and applications ⋮ Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Circle graphs and monadic second-order logic ⋮ Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width ⋮ A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs ⋮ Equistable distance-hereditary graphs ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Rooted directed path graphs are leaf powers ⋮ Recent developments on graphs of bounded clique-width ⋮ Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width ⋮ Distance-hereditary graphs are clique-perfect ⋮ Boundary properties of graphs for algorithmic graph problems ⋮ Split permutation graphs ⋮ 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 ⋮ Vertex disjoint paths on clique-width bounded graphs ⋮ On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph ⋮ Compact representation of graphs of small clique-width ⋮ Mim-width. II. The feedback vertex set problem ⋮ Clique-width of graphs defined by one-vertex extensions ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Cluster deletion on interval graphs and split related graphs ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection 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
This page was built for publication: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
