Polynomially solvable cases for the maximum stable set problem

DOI10.1016/0166-218X(94)00051-EzbMath0830.68099MaRDI QIDQ1894362

Alain Hertz

Publication date: 6 September 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

stable setstability numberpolynomial algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (17)

On the use of Boolean methods for the computation of the stability number ⋮ Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs ⋮ Struction revisited ⋮ Stability preserving transformations of graphs ⋮ Unnamed Item ⋮ A polynomial algorithm to find an independent set of maximum weight in a fork-free graph ⋮ A note on \(\alpha\)-redundant vertices in graphs ⋮ New potential functions for greedy independence and coloring ⋮ Weighted stability number of graphs and weighted satisfiability: the two facets of pseudo-Boolean optimization ⋮ Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems ⋮ Pseudo-Boolean optimization ⋮ Augmenting graphs for independent sets ⋮ Augmenting chains in graphs without a skew star. ⋮ On the complexity of the independent set problem in triangle graphs ⋮ GreedyMAX-type Algorithms for the Maximum Independent Set Problem ⋮ Stability in \(P_5\)- and banner-free graphs ⋮ On the stable set problem in special \(P_{5}\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stability in CAN-free graphs
• The struction of a graph: Application to CN-free graphs
• Quelques utilisations de la STRUCTION. (Some applications of STRUCTION)
• Matching theory
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Stability number of bull- and chair-free graphs
• STABULUS: A technique for finding stable sets in large graphs with tabu search
• Tabu Search—Part I
• `` Strong NP-Completeness Results
• On the stability number of AH‐free graphs

This page was built for publication: Polynomially solvable cases for the maximum stable set problem