On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
From MaRDI portal
Publication:2465646
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
- On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
- New applications of clique separator decomposition for the maximum weight stable set problem
- Fundamentals of Computation Theory
- Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
- scientific article; zbMATH DE number 1839471
Cites work
- A classification of certain graphs with minimal imperfection properties
- A New Algorithm for Generating All the Maximal Independent Sets
- A note on -redundant vertices in graphs
- Algorithms for weakly triangulated graphs
- An upper bound on the number of cliques in a graph
- Augmenting graphs for independent sets
- Decomposition by clique separators
- Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
- Four classes of perfectly orderable graphs
- Fundamentals of Computation Theory
- Graph Classes: A Survey
- Holes and dominoes in Meyniel graphs
- scientific article; zbMATH DE number 3904619 (Why is no real title available?)
- scientific article; zbMATH DE number 3906240 (Why is no real title available?)
- scientific article; zbMATH DE number 3513839 (Why is no real title available?)
- scientific article; zbMATH DE number 861332 (Why is no real title available?)
- scientific article; zbMATH DE number 1445284 (Why is no real title available?)
- Modular decomposition and transitive orientation
- On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
- On diameters and radii of bridged graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- On generating all maximal independent sets
- On graphs with polynomially solvable maximum-weight clique problem
- On linear and circular structure of (claw, net)-free graphs
- Recognizing weakly triangulated graphs by edge separability
- Stability in \(P_5\)- and banner-free graphs
- Stability in CAN-free graphs
- Stability in circular arc graphs
- Stable sets in certain \(P_6\)-free graphs
- The ellipsoid method and its consequences in combinatorial optimization
- The strong perfect graph theorem
- The struction of a graph: Application to CN-free graphs
Cited in
(44)- An introduction to clique minimal separator decomposition
- Computing a clique tree with the algorithm maximal label search
- Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
- Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
- An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)
- Approximation of knapsack problems with conflict and forcing graphs
- Colouring square-free graphs without long induced paths
- The maximum independent set problem in subclasses of subcubic graphs
- Applying clique-decomposition for computing Gromov hyperbolicity
- Independent sets in some classes of \(S_{i,j,k}\)-free graphs
- The stable set problem: clique and nodal inequalities revisited
- Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
- Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
- Weighted independent sets in classes of \(P_6\)-free graphs
- Parameterized algorithms for the independent set problem in some hereditary graph classes
- scientific article; zbMATH DE number 4134082 (Why is no real title available?)
- Colouring square-free graphs without long induced paths
- Complexity of coloring graphs without paths and cycles
- On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
- On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
- Organizing the atoms of the clique separator decomposition into an atom tree
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
- Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Feedback vertex set and even cycle transversal for H-free graphs: finding large block graphs
- Complexity and polynomially solvable special cases of QUBO
- Square-Free Graphs with No Six-Vertex Induced Path
- Fundamentals of Computation Theory
- Induced disjoint paths and connected subgraphs for H-free graphs
- Combining decomposition approaches for the maximum weight stable set problem
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- On graphs with no induced five‐vertex path or paraglider
- Clique‐width: Harnessing the power of atoms
- Strengthening Brooks' chromatic bound on \(P_6\)-free graphs
- -boundedness and related problems on graphs without long induced paths: a survey
- Maximum weight independent sets in hole- and dart-free graphs
- On distance-3 matchings and induced matchings
- Graphs without large apples and the maximum weight independent set problem
- Maximum weight independent sets in hole- and co-chair-free graphs
- On the maximum independent set problem in graphs of bounded maximum degree
- New applications of clique separator decomposition for the maximum weight stable set problem
- Weighted independent sets in a subclass of P₆-free graphs
- Weighted efficient domination in two subclasses of P₆-free graphs
This page was built for publication: On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2465646)
