The struction of a graph: Application to CN-free graphs

DOI10.1007/BF02579377zbMath0582.05051OpenAlexW2029454721MaRDI QIDQ1068855

N. V. R. Mahadev, Dominique de Werra, Peter L. Hammer

Publication date: 1985

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579377

zbMATH Keywords

stability numberpolynomial time algorithmnetclawCN-free graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

Quelques utilisations de la STRUCTION. (Some applications of STRUCTION), The struction algorithm for the maximum stable set problem revisited, On the vertex packing problem, Polynomially solvable cases for the maximum stable set problem, On independent vertex sets in subclasses of apple-free graphs, Claw-free graphs---a survey, On the use of Boolean methods for the computation of the stability number, New applications of clique separator decomposition for the maximum weight stable set problem, On linear and circular structure of (claw, net)-free graphs, On Hamiltonicity of \{claw, net\}-free graphs, Struction revisited, Stability preserving transformations of graphs, Hamiltonicity in claw-free graphs, On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, New potential functions for greedy independence and coloring, Weighted stability number of graphs and weighted satisfiability: the two facets of pseudo-Boolean optimization, Stability number of bull- and chair-free graphs, Pseudo-Boolean optimization, Consensus algorithms for the generation of all maximal bicliques, Local transformations of graphs preserving independence number

Cites Work

• Unnamed Item
• Stability in CAN-free 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é