Stability preserving transformations of graphs

DOI10.1007/S10479-008-0395-1MaRDI QIDQ646718zbMATH OpenOpenAlexFDO

Authors Vadim 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

graph transformationmaximum stable set problemstability numberstable set of verticestransformations

Mathematics Subject Classification ID

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

Recommendations

• Graph transformations preserving the stability number
• Graph transformations preserving the stability number
• Publication:4505839
• Conic reduction of graphs for the stable set problem
• scientific article; zbMATH DE number 2196278

Cites work

• A class of perfectly contractile graphs
• A note on -redundant vertices in graphs
• A transformation which preserves the clique number
• An augmentation algorithm for the maximum weighted stable set problem
• Computing independent sets in graphs with large girth
• Conic reduction of graphs for the stable set problem
• Graph Classes: A Survey
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 3904619 (Why is no real title available?)
• scientific article; zbMATH DE number 3943843 (Why is no real title available?)
• scientific article; zbMATH DE number 1305487 (Why is no real title available?)
• scientific article; zbMATH DE number 1512194 (Why is no real title available?)
• scientific article; zbMATH DE number 956849 (Why is no real title available?)
• Local transformations of graphs preserving independence number
• Matching theory
• Measure and conquer
• On Some Properties of the Struction of a Graph
• On the stability number of AH‐free graphs
• On the use of Boolean methods for the computation of the stability number
• Polynomially solvable cases for the maximum stable set problem
• Pseudo-Boolean optimization
• Quelques utilisations de la STRUCTION. (Some applications of STRUCTION)
• Réductions et conditions d'optimalité dans le problème de l'ensemble stable de poids maximal
• Stability in CAN-free graphs
• Stability in circular arc graphs
• Stability number of bull- and chair-free graphs
• Struction revisited
• The struction algorithm for the maximum stable set problem revisited
• The struction of a graph: Application to CN-free graphs
• Transformations which Preserve Perfectness and H-Perfectness of Graphs
• Vertex cover: Further observations and further improvements
• Weighted stability number of graphs and weighted satisfiability: the two facets of pseudo-Boolean optimization

Cited in

(13)

• Conic reduction of graphs for the stable set problem
• Graph transformations for efficient structural analysis
• 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
• Local transformations of graphs preserving independence number
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• scientific article; zbMATH DE number 1512194 (Why is no real title available?)
• scientific article; zbMATH DE number 2196278 (Why is no real title available?)
• Graph transformations preserving the stability number
• Graph transformations preserving the stability number
• The minimum-cost transformation of graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q646718)