Independent set in k-Claw-Free Graphs: Conditional χ-boundedness and the Power of LP/SDP Relaxations.
Parinya ChalermsookAmeet GadekarKamyar KhodamoradiJoachim SpoerhasePublished in: CoRR (2023)
Keyphrases
- independent set
- linear programming
- semidefinite programming
- maximum independent set
- semidefinite
- linear program
- semi definite programming
- np hard
- maximum weight
- convex relaxation
- lp relaxation
- sufficient conditions
- semi infinite
- integer programming
- linear programming relaxation
- lower bound
- objective function
- column generation
- graph theory
- feasible solution
- graph theoretic