✦ LIBER ✦

Graph substitution and set packing polytopes

✍ Scribed by E. Balas; E. Zemel

Publisher: John Wiley and Sons
Year: 1977
Tongue: English
Weight: 599 KB
Volume: 7
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230070307

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Facets of the set packing polytope provide strong cutting planes for set packing and partitioning problems. Set packing polytopes are in a one‐to‐one correspondence with graphs. The facets of P(G), the set packing polytope associated with the graph G, are related to certain subgraphs of G. Of particular interest are those subgraphs G′ which are facet producing, i.e., which give rise to facets of P(G′) that cannot be obtained by lifting a facet of P(G′ ‐ {x}), for any vertex x of G′. In this paper we characterize the facets of the set packing polytopes associated with the class of graphs obtained by Chvátal's substitution procedure, and give necessary and sufficient conditions for these graphs to be facet‐producing.

📜 SIMILAR VOLUMES

Coloring planar Toeplitz graphs and the

Coloring planar Toeplitz graphs and the stable set polytope

✍ Reinhardt Euler 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 290 KB

Cliques and odd cycles are well known to induce facet-deÿning inequalities for the stable set polytope. In graph coloring cliques are a class of n-critical graphs whereas odd cycles represent the class of 3-critical graphs. In the ÿrst part of this paper we generalize both notions to (Kn \ e)-cycles

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 facets of the stable set polytope

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

✍ Gautier Stauffer 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 237 KB

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

Representations of polytopes and polyhed

Representations of polytopes and polyhedral sets

✍ P. Mcmullen 📂 Article 📅 1973 🏛 Springer 🌐 English ⚖ 824 KB

Interchange graphs and the Hamiltonian c

Interchange graphs and the Hamiltonian cycle polytope

✍ Gerard Sierksma 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 464 KB

This paper answers the (non)adjacency question for the whole spectrum of Hamiltonian cycles on the Hamiltonian cycle polytope (HC-polytope), also called the symmetric traveling salesman polytope, namely from Hamiltonian cycles that differ in only two edges through Hamiltonian cycles that are edge di