Stability preserving transformations of graphs
From MaRDI portal
Publication:646718
DOI10.1007/s10479-008-0395-1zbMath1250.05083MaRDI QIDQ646718
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
transformations; stability number; graph transformation; maximum stable set problem; stable set of vertices
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, 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