Independent Set in k-Claw-Free Graphs: Conditional χ-Boundedness and the Power of LP/SDP Relaxations.
Parinya ChalermsookAmeet GadekarKamyar KhodamoradiJoachim SpoerhasePublished in: WAOA (2023)
Keyphrases
- independent set
- linear programming
- semidefinite programming
- semidefinite
- maximum independent set
- linear program
- semi infinite
- sufficient conditions
- np hard
- semi definite programming
- maximum weight
- interior point methods
- lp relaxation
- primal dual
- convex relaxation
- optimal solution
- lower bound
- linear programming relaxation
- feasible solution
- graph theoretic
- integer programming
- bipartite graph