On the facets of the lift-and-project relaxations of graph subdivisions |
| |
| Affiliation: | 2. CONICET and Universidad Nacional de Rosario, Argentina;1. Nuclear Dynamics Programme, Babraham Institute, Cambridge CB22 3AT, UK;2. Cambridge Systems Biology Centre, University of Cambridge, Tennis Court Road, Cambridge CB2 1QR, UK;1. Department of Industrial Engineering, University of Padova, Padova 35131, Italy;2. Advanced Power and Energy Center, ECE Department, KUST, Abu Dhabi, United Arab Emirates;3. Advanced High Voltage Engineering Research Centre, Cardiff University, Cardiff, UK;1. UFPA, Rua Augusto Correa, No 01, Campus Universitário do Guamá, Belem, 66075110, Brazil;2. University of Florida, 553 Engeniring Bulding, Gainesville, 32611, United States;3. Moscow Institute of Electronics and Mathematics, National Research University Higher School of Economics, Moscow, Russia |
| |
| Abstract: | We study the behavior of lift-and-project procedures for solving combinatorial optimization problems as described by Lovász and Schrijver (1991), in the context of the stable set problem on graphs. Following the work of Wolsey (1976), we investigate how to generate facets of the relaxations obtained by these procedures from facets of the relaxations of the original graph, after applying fundamental graph operations. We show our findings for the odd subdivision of an edge and its generalization, the stretching of a vertex operation. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
