Conic reduction of graphs for the stable set problem

DOI10.1016/S0012-365X(99)00408-2MaRDI QIDQ1579563zbMATH OpenOpenAlexFDO

Authors Vadim Lozin

Publication date 12 March 2001

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00408-2

zbMATH Keywords

graph transformationsmaximum stable set problempolynomial algorithmstability number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Stability preserving transformations of graphs
• Stability number of bull- and chair-free graphs
• Publication:4505839
• Reductions for the stable set problem
• scientific article; zbMATH DE number 1208717

Cited in

(9)

• Structure and stability number of chair-, co-P- and gem-free graphs revisited
• Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
• Chair-free Berge graphs are perfect
• Struction revisited
• A note on the Cornaz-Jost transformation to solve the graph coloring problem
• Reductions for the stable set problem
• Graph transformations preserving the stability number
• Graph transformations preserving the stability number
• Stability preserving transformations of graphs

This page was built for publication: Conic reduction of graphs for the stable set problem

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