# Clique-connecting forest and stable set polytopes

RAIRO - Operations Research (2010)

- Volume: 44, Issue: 1, page 73-83
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topCornaz, Denis. "Clique-connecting forest and stable set polytopes." RAIRO - Operations Research 44.1 (2010): 73-83. <http://eudml.org/doc/250831>.

@article{Cornaz2010,

abstract = {
Let G = (V,E) be a simple undirected graph.
A forest F ⊆ E of G is said to be clique-connecting if each tree of F spans a clique of G.
This paper adresses the clique-connecting forest polytope.
First we give a formulation and a polynomial time separation algorithm.
Then we show that the nontrivial nondegenerate facets of the stable set polytope are facets of the clique-connecting polytope.
Finally we introduce a family of rank inequalities which are facets, and which generalize the clique inequalities.
},

author = {Cornaz, Denis},

journal = {RAIRO - Operations Research},

keywords = {Graph; polytope; separation; facet; graph},

language = {eng},

month = {2},

number = {1},

pages = {73-83},

publisher = {EDP Sciences},

title = {Clique-connecting forest and stable set polytopes},

url = {http://eudml.org/doc/250831},

volume = {44},

year = {2010},

}

TY - JOUR

AU - Cornaz, Denis

TI - Clique-connecting forest and stable set polytopes

JO - RAIRO - Operations Research

DA - 2010/2//

PB - EDP Sciences

VL - 44

IS - 1

SP - 73

EP - 83

AB -
Let G = (V,E) be a simple undirected graph.
A forest F ⊆ E of G is said to be clique-connecting if each tree of F spans a clique of G.
This paper adresses the clique-connecting forest polytope.
First we give a formulation and a polynomial time separation algorithm.
Then we show that the nontrivial nondegenerate facets of the stable set polytope are facets of the clique-connecting polytope.
Finally we introduce a family of rank inequalities which are facets, and which generalize the clique inequalities.

LA - eng

KW - Graph; polytope; separation; facet; graph

UR - http://eudml.org/doc/250831

ER -

## References

top- M. Campêlo, R. Corrêa and Y. Frota, Cliques, holes and the vertex coloring polytope. Inf. Process. Lett.89 (2004) 159–164. Zbl1176.90598
- D. Cornaz and V. Jost, A one-to-one correspondence beetween stables sets and colorings. Oper. Res. Lett.36 (2008) 673–676. Zbl1152.05327
- E. Cheng and W.H. Cunningham, Wheel inequalitites for stable set polytopes. Math. Program.77 (1997) 389–421. Zbl0891.90161
- J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices. Journal of Resarch National Bureau of Standards Section B69 (1965) 67–72. Zbl0141.21802
- J. Edmonds, Matroids and the greedy algorithm. Math. Program.1 (1971) 127–136. Zbl0253.90027
- M. Grötschel, L. Lovàsz and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica1 (1981) 169–197. Zbl0492.90056
- M.W. Padberg, On the facial structure of set packing polyhedra. Math. Program.5 (1973) 199–215. Zbl0272.90041
- M.W. Padberg and L.A. Wolsey, Fractional covers for forests and matchings. Math. Program.29 (1984) 1–14. Zbl0532.90073
- J.-C. Picard and M. Queyranne, Selected applications of minimum cuts in networks. INFOR Can. J. Oper. Res. Inf. Process.20 (1982) 394–422. Zbl0501.90069
- J.M.W. Rhys, A selection problem of shared fixed costs and network flows. Manag. Sci.17 (1970) 200–207.
- A. Schrijver, Combinatorial Optimization. Springer-Verlag, Berlin, Heidelberg (2003). Zbl1041.90001

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.