Vertices Belonging to All or to No Maximum Stable Sets of a Graph
From MaRDI portal
Publication:3960467
DOI10.1137/0603052zbMath0496.90056MaRDI QIDQ3960467
Peter L. Hammer, Pierre Hansen, Bruno Simeone
Publication date: 1982
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0603052
Related Items
Polynomial time recognition of essential graphs having stability number equal to matching number, Pseudo-Boolean optimization, A network approach for specially structured linear programs arising in 0-1 quadratic optimization, Vertices contained in all or in no minimum paired-dominating set of a tree, Persistency and matroid intersection, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, The maximum clique problem, Combinatorial properties of the family of maximum stable sets of a graph, König-Egerváry graphs, 2-bicritical graphs and fractional matchings, On the number of vertices belonging to all maximum stable sets of a graph, Crown reductions for the minimum weighted vertex cover problem, On \(\alpha\)-critical edges in König--Egerváry graphs, Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions, Vizing's conjecture: a survey and recent results, Vertices contained in all minimum paired-dominating sets of a tree, Roof duality, complementation and persistency in quadratic 0–1 optimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Regularisable graphs I
- Regularisable graphs, II
- Minimum node covers and 2-bicritical graphs
- Packing Problems and Hypergraph Theory: A Survey
- Vertex packings: Structural properties and algorithms
- On the integer-valued variables in the linear vertex packing problem
- Integer Programming: Methods, Uses, Computations
- The complexity of theorem-proving procedures
- The Factors of Graphs
