New applications of clique separator decomposition for the maximum weight stable set problem
type: Item
instance of: scholarly article
title: New applications of clique separator decomposition for the maximum weight stable set problem
zbMATH Open document ID: 1118.68101
author: Van Bang Le
author: Suhail Mahfud
author: Andreas Brandstädt
published in: Theoretical Computer Science
publication date: 2007-02-26T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 5129793
zbMATH Keywords: Maximum Stable Set problem
zbMATH Keywords: clique separators in graphs
zbMATH Keywords: graph decompositions
zbMATH Keywords: \(P_{5}\)-free graphs
zbMATH Keywords: efficient graph algorithms
MaRDI profile type: Publication
full work available at URL: j.tcs.2006.10.035
OpenAlex ID: W1998462868
cites work: Polynomial algorithm for finding the largest independent sets in graphs without forks
cites work: On easy and hard hereditary classes of graphs with respect to the independent set problem
cites work: On (\(P_{5}\), diamond)-free graphs
cites work: On graphs with polynomially solvable maximum-weight clique problem
cites work: A nice class for the vertex packing problem
cites work: On algorithms for (\(P_5\), gem)-free graphs
cites work: Q3145799
cites work: (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
cites work: On linear and circular structure of (claw, net)-free graphs
cites work: On the stability number of claw-free \(P_5\)-free and more general graphs
cites work: On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
cites work: Stability number of bull- and chair-free graphs revisited
cites work: On the structure of (\(P_{5}\),\,gem)-free graphs
cites work: Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
cites work: On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs
cites work: Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
cites work: Structure and stability number of chair-, co-P- and gem-free graphs revisited
cites work: A note on \(\alpha\)-redundant vertices in graphs
cites work: Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
cites work: On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
cites work: Arboricity and Subgraph Listing Algorithms
cites work: The complexity of generalized clique packing
cites work: Q3676177
cites work: On the vertex packing problem
cites work: Stability number of bull- and chair-free graphs
cites work: On diameters and radii of bridged graphs
cites work: An upper bound on the number of cliques in a graph
cites work: A transformation which preserves the clique number
cites work: \(P_{5}\)-free augmenting graphs and the maximum stable set problem
cites work: Robust algorithms for the stable set problem
cites work: On the stable set problem in special \(P_{5}\)-free graphs
cites work: Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
cites work: Stability in circular arc graphs
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Stability in CAN-free graphs
cites work: The struction of a graph: Application to CN-free graphs
cites work: Stability in \(P_5\)- and banner-free graphs
cites work: Modular decomposition and transitive orientation
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: Q3683903
cites work: Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
cites work: Stable sets in certain \(P_6\)-free graphs
cites work: Some results on maximum stable sets in certain \(P_{5}\)-free graphs
cites work: Computing independent sets in graphs with large girth
cites work: Q4770411
cites work: Q4871056
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
cites work: Decomposition by clique separators
cites work: A New Algorithm for Generating All the Maximal Independent Sets
cites work: Q3686753
DOI: 10.1016/J.TCS.2006.10.035
description: scientific article; zbMATH DE number 5129793