𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the facets of the stable set polytope of quasi-line graphs

✍ Scribed by Gautier Stauffer

Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
237 KB
Volume
39
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Clique family inequalities for the stabl
Clique family inequalities for the stable set polytope of quasi-line graphs
✍ G. Oriolo πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 248 KB

In one of fundamental works in combinatorial optimization, Edmonds gave a complete linear description of the matching polytope. Matchings in a graph are equivalent to stable sets in its line graph. Also the neighborhood of any vertex in a line graph partitions into two cliques: graphs with this latt

Stability critical graphs and ranks face
Stability critical graphs and ranks facets of the stable set polytope
✍ E.C. Sewell; L.E. Trotter Jr. πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 616 KB

Rank inequalities due to stability critical (u-critical) graphs are used to develop a finite nested sequence of linear relaxations of the stable set polytope, the strongest of which provides an integral max-min relation: In a simple graph, the maximum size of a stable set is equal to the minimum (we

On the cycle polytope of a directed grap
On the cycle polytope of a directed graph
✍ Egon Balas; Maarten Oosten πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 185 KB πŸ‘ 2 views
Upper Bounds on the Maximal Number of Fa
Upper Bounds on the Maximal Number of Facets of 0/1-Polytopes
✍ TamΓ‘s Fleiner; Volker Kaibel; GΓΌnter Rote πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 157 KB

We prove two new upper bounds on the number of facets that a d-dimensional 0/1-polytope can have. The first one is 2(d -1)!+2(d -1) (which is the best one currently known for small dimensions), while the second one of O((d -2)!) is the best known bound for large dimensions.