Finding maximum subgraphs with relatively large vertex connectivity
We discuss clique relaxation models based on relative vertex connectivity. We show relations between problem complexity and vertex connectivity requirements. The proposed generalization encompasses previously known models. We develop mixed integer programs and exact algorithms for the proposed models. We illustrate properties of the proposed models with computational experiments.
vertex connectivity clique relaxations mixed integer programming computational complexity 2-club