Vertices Belonging to All or to No Maximum Stable Sets of a Graph

DOI10.1137/0603052zbMath0496.90056OpenAlexW2090526848MaRDI QIDQ3960467

Pierre Hansen, Peter L. Hammer, 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

zbMATH Keywords

continuous relaxationset of optimal solutionsmaximum weighted stable set problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Boolean programming (90C09)

Related Items

Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree, Combinatorial properties of the family of maximum stable sets of a graph, On vertices contained in all or in no metric basis, A polytime preprocess algorithm for the maximum independent set problem, Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Polynomial time recognition of essential graphs having stability number equal to matching number, A network approach for specially structured linear programs arising in 0-1 quadratic optimization, Crown reductions for the minimum weighted vertex cover problem, Pseudo-Boolean optimization, On \(\alpha\)-critical edges in König--Egerváry graphs, Contraction and deletion blockers for perfect graphs and \(H\)-free graphs, Edges contained in all or in no minimum edge dominating set of a tree, Vertices contained in all or in no minimum paired-dominating set of a tree, Vertices contained in all minimum paired-dominating sets of a tree, König-Egerváry graphs, 2-bicritical graphs and fractional matchings, Persistency and matroid intersection, Vizing's conjecture: a survey and recent results, Smaller Parameters for Vertex Cover Kernelization, On the number of vertices belonging to all maximum stable sets of a graph, The maximum clique problem, Roof duality, complementation and persistency in quadratic 0–1 optimization, Persistency of linear programming relaxations for the stable set problem, Safety in \(s\)-\(t\) paths, trails and walks

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