Stability preserving transformations of graphs

DOI10.1007/s10479-008-0395-1zbMath1250.05083MaRDI QIDQ646718

Vadim V. Lozin

Publication date: 17 November 2011

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-008-0395-1

zbMATH Keywords

transformations; stability number; graph transformation; maximum stable set problem; stable set of vertices

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number, New sufficient conditions for \(\alpha\)-redundant vertices, The maximum independent set problem in subclasses of subcubic graphs, From matchings to independent sets, Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weighted stability number of graphs and weighted satisfiability: the two facets of pseudo-Boolean optimization
• Pseudo-Boolean optimization
• 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
• Computing independent sets in graphs with large girth
• Stability number of bull- and chair-free graphs
• The struction algorithm for the maximum stable set problem revisited
• On the use of Boolean methods for the computation of the stability number
• Struction revisited
• Conic reduction of graphs for the stable set problem
• An augmentation algorithm for the maximum weighted stable set problem
• A transformation which preserves the clique number
• Polynomially solvable cases for the maximum stable set problem
• A class of perfectly contractile graphs
• Vertex Cover: Further Observations and Further Improvements
• On Some Properties of the Struction of a Graph
• Measure and conquer
• Stability in circular arc graphs
• Réductions et conditions d'optimalité dans le problème de l'ensemble stable de poids maximal
• Transformations which Preserve Perfectness and H-Perfectness of Graphs
• Local transformations of graphs preserving independence number
• Graph Classes: A Survey
• On the stability number of AH‐free graphs
• A note on \(\alpha\)-redundant vertices in graphs