تقرير
Lov\'asz-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
| العنوان: | Lov\'asz-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs |
|---|---|
| المؤلفون: | Bianchi, S., Escalante, M., Nasini, G., Tunçel, L. |
| سنة النشر: | 2014 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, Mathematics - Optimization and Control |
| الوصف: | We study the Lov\'asz-Schrijver lift-and-project operator ($LS_+$) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the $LS_+$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs $LS_+$-perfect. In the current contribution, we pursue a full combinatorial characterization of $LS_+$-perfect graphs and make progress towards such a characterization by establishing a new, close relationship among $LS_+$-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs. Comment: 20 pages, 4 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1411.2069 |
| رقم الأكسشن: | edsarx.1411.2069 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |