تقرير
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 |
الوصف غير متاح. |