Clique-connecting forest and stable set polytopes

Denis Cornaz

RAIRO - Operations Research (2010)

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

Abstract

top
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.

How to cite

top

Cornaz, 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
  1. 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
  2. D. Cornaz and V. Jost, A one-to-one correspondence beetween stables sets and colorings. Oper. Res. Lett.36 (2008) 673–676.  Zbl1152.05327
  3. E. Cheng and W.H. Cunningham, Wheel inequalitites for stable set polytopes. Math. Program.77 (1997) 389–421.  Zbl0891.90161
  4. 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
  5. J. Edmonds, Matroids and the greedy algorithm. Math. Program.1 (1971) 127–136.  Zbl0253.90027
  6. M. Grötschel, L. Lovàsz and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica1 (1981) 169–197.  Zbl0492.90056
  7. M.W. Padberg, On the facial structure of set packing polyhedra. Math. Program.5 (1973) 199–215.  Zbl0272.90041
  8. M.W. Padberg and L.A. Wolsey, Fractional covers for forests and matchings. Math. Program.29 (1984) 1–14.  Zbl0532.90073
  9. 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
  10. J.M.W. Rhys, A selection problem of shared fixed costs and network flows. Manag. Sci.17 (1970) 200–207.  
  11. A. Schrijver, Combinatorial Optimization. Springer-Verlag, Berlin, Heidelberg (2003).  Zbl1041.90001

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.