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
topHow 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.
- D. Cornaz and V. Jost, A one-to-one correspondence beetween stables sets and colorings. Oper. Res. Lett.36 (2008) 673–676.
- E. Cheng and W.H. Cunningham, Wheel inequalitites for stable set polytopes. Math. Program.77 (1997) 389–421.
- J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices. Journal of Resarch National Bureau of Standards Section B69 (1965) 67–72.
- J. Edmonds, Matroids and the greedy algorithm. Math. Program.1 (1971) 127–136.
- M. Grötschel, L. Lovàsz and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica1 (1981) 169–197.
- M.W. Padberg, On the facial structure of set packing polyhedra. Math. Program.5 (1973) 199–215.
- M.W. Padberg and L.A. Wolsey, Fractional covers for forests and matchings. Math. Program.29 (1984) 1–14.
- J.-C. Picard and M. Queyranne, Selected applications of minimum cuts in networks. INFOR Can. J. Oper. Res. Inf. Process.20 (1982) 394–422.
- 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).
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.