Stability preserving transformations of graphs

DOI10.1007/s10479-008-0395-1zbMath1250.05083OpenAlexW2081200856MaRDI 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

transformationsstability numbergraph transformationmaximum stable set problemstable set of vertices

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

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

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

This page was built for publication: Stability preserving transformations of graphs