Clique family inequalities for the stable set polytope of quasi-line graphs.

DOI10.1016/S0166-218X(03)00400-1zbMath1052.90108MaRDI QIDQ1414593

D. Massart

Publication date: 4 December 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Polyhedral combinatoricsClaw-free graphsMatching polytopeQuasi-line graphs

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Persistency of Linear Programming Relaxations for the Stable Set Problem ⋮ On the feedback vertex set polytope of a series-parallel graph ⋮ Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs ⋮ Minor related row family inequalities for the set covering polyhedron of circulant matrices ⋮ A construction for non-rank facets of stable set polytopes of webs ⋮ On dominating set polyhedra of circular interval graphs ⋮ Facet-inducing web and antiweb inequalities for the graph coloring polytope ⋮ On the facets of stable set polytopes of circular interval graphs ⋮ The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect ⋮ The stable set polytope of icosahedral graphs ⋮ On the facets of the stable set polytope of quasi-line graphs ⋮ 2-clique-bond of stable set polyhedra ⋮ A note on the Chvátal-rank of clique family inequalities ⋮ Clique-circulants and the stable set polytope of fuzzy circular interval graphs ⋮ The stable set polytope of quasi-line graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On non-rank facets of stable set polytopes of webs with clique number four ⋮ Gear composition and the stable set polytope ⋮ The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are \(\mathcal{G}\)-perfect ⋮ Strengthened clique-family inequalities for the stable set polytope ⋮ Unnamed Item ⋮ Almost all webs are not rank-perfect ⋮ Generalized clique family inequalities for claw-free graphs ⋮ On facets of stable set polytopes of claw-free graphs with stability number three ⋮ Persistency of linear programming relaxations for the stable set problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching theory
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs
• On stable set polyhedra for K//(1,3)free graphs
• Geometric algorithms and combinatorial optimization
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• A class of facet producing graphs for vertex packing polyhedra
• The rank facets of the stable set polytope for claw-free graphs
• Polyhedral characterizations and perfection of line graphs
• On certain polytopes associated with graphs
• Line graphs and forbidden induced subgraphs
• Applying Lehman's theorems to packing problems
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Graphe représentatif des arêtes d'un multigraphe
• Edmonds polytopes and a hierarchy of combinatorial problems
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Stable Set Polytopes for a Class of Circulant Graphs
• On the facial structure of set packing polyhedra
• Maximum matching and a polyhedron with 0,1-vertices