New applications of clique separator decomposition for the maximum weight stable set problem
From MaRDI portal
Publication:868954
DOI10.1016/j.tcs.2006.10.035zbMath1118.68101OpenAlexW1998462868MaRDI QIDQ868954
Suhail Mahfud, Van Bang Le, Andreas Brandstädt
Publication date: 26 February 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2006.10.035
graph decompositions\(P_{5}\)-free graphsclique separators in graphsefficient graph algorithmsMaximum Stable Set problem
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (9)
Weighted independent sets in classes of \(P_6\)-free graphs ⋮ On independent vertex sets in subclasses of apple-free graphs ⋮ 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 ⋮ Complexity results for equistable graphs and related classes ⋮ Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs ⋮ On stable cutsets in claw-free graphs and planar graphs ⋮ Maximum weight independent sets in hole- and dart-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
- Stability in CAN-free graphs
- On algorithms for (\(P_5\), gem)-free graphs
- Structure and stability number of chair-, co-P- and gem-free graphs revisited
- Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
- Decomposition by clique separators
- The struction of a graph: Application to CN-free graphs
- The complexity of generalized clique packing
- On diameters and radii of bridged graphs
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- The ellipsoid method and its consequences in combinatorial optimization
- Computing independent sets in graphs with large girth
- Stability number of bull- and chair-free graphs
- Modular decomposition and transitive orientation
- On the stability number of claw-free \(P_5\)-free and more general graphs
- Stable sets in certain \(P_6\)-free graphs
- A nice class for the vertex packing problem
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
- On linear and circular structure of (claw, net)-free graphs
- Stability number of bull- and chair-free graphs revisited
- Robust algorithms for the stable set problem
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- \(P_{5}\)-free augmenting graphs and the maximum stable set problem
- Some results on maximum stable sets in certain \(P_{5}\)-free graphs
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- Stability in \(P_5\)- and banner-free graphs
- On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs
- On (\(P_{5}\), diamond)-free graphs
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- A transformation which preserves the clique number
- Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
- On the stable set problem in special \(P_{5}\)-free graphs
- On the vertex packing problem
- On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
- Arboricity and Subgraph Listing Algorithms
- Stability in circular arc graphs
- On graphs with polynomially solvable maximum-weight clique problem
- A New Algorithm for Generating All the Maximal Independent Sets
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- An upper bound on the number of cliques in a graph
- A note on \(\alpha\)-redundant vertices in graphs
This page was built for publication: New applications of clique separator decomposition for the maximum weight stable set problem
