Polynomially solvable cases for the maximum stable set problem
type: Item
instance of: scholarly article
title: Polynomially solvable cases for the maximum stable set problem
zbMATH Open document ID: 0830.68099
DOI: 10.1016/0166-218X(94)00051-E
author: Alain Hertz
published in: Discrete Applied Mathematics
publication date: 1995-09-06T00:00:00Z
review text: A set \(S\) of vertices in a graph \(G= (V, E)\) is stable if no two vertices in \(S\) are linked by an edge. The size of a maximum stable set in \(G\) is denoted \(\alpha(G)\) and is called the stability number of \(G\). The author describes two classes of graphs for which the stability number can be computed in polynomial time. For one class, an iterative procedure can be used. At each step, the iteration builds from a graph \(G\) a new graph \(G'\) which has fewer vertices and has the property that \(\alpha(G')= \alpha(G)- 1\). For the other class, the existence of a stable set of given size \(k\) can be determined in polynomial time.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 777824
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: stable set
zbMATH Keywords: stability number
MaRDI profile type: Publication
cites work: Q5615282
cites work: Stability number of bull- and chair-free graphs
cites work: Q3682509
cites work: STABULUS: A technique for finding stable sets in large graphs with tabu search
cites work: `` Strong '' NP-Completeness Results
cites work: Tabu Search—Part I
cites work: Q3216686
cites work: Stability in CAN-free graphs
cites work: The struction of a graph: Application to CN-free graphs
cites work: On the stability number of AH‐free graphs
cites work: Quelques utilisations de la STRUCTION. (Some applications of STRUCTION)
cites work: Matching theory
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
description: scientific article; zbMATH DE number 777824