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

DOI10.1016/S0166-218X(03)00400-1zbMATH Open1052.90108MaRDI QIDQ1414593FDOQ1414593

Authors: D. Massart 

Publication date: 4 December 2003

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

Recommendations

• Generalized clique family inequalities for claw-free graphs
• The stable set polytope of quasi-line graphs
• On the facets of stable set polytopes of circular interval graphs
• On the facets of the stable set polytope of quasi-line graphs
• Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs

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)

Cites Work

• Matching theory
• Geometric algorithms and combinatorial optimization
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• A class of facet producing graphs for vertex packing polyhedra
• On certain polytopes associated with graphs
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Title not available (Why is that?)
• On the facial structure of set packing polyhedra
• Maximum matching and a polyhedron with 0,1-vertices
• Title not available (Why is that?)
• On maximal independent sets of vertices in claw-free graphs
• Graphe représentatif des arêtes d'un multigraphe
• On stable set polyhedra for K//(1,3)free graphs
• The rank facets of the stable set polytope for claw-free graphs
• Line graphs and forbidden induced subgraphs
• Applying Lehman's theorems to packing problems
• Stable Set Polytopes for a Class of Circulant Graphs
• 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
• Polyhedral characterizations and perfection of line graphs
• Title not available (Why is that?)
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Mobility models for cellular mobile radiotelephone networks: Product forms and blocking
• Title not available (Why is that?)
• Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs

Cited In (30)

• Almost all webs are not rank-perfect
• The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect
• Strengthened clique-family inequalities for 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
• Persistency of linear programming relaxations for the stable set problem
• Persistency of linear programming relaxations for the stable set problem
• Gear composition and the stable set polytope
• The stable set polytope of claw-free graphs with large stability number
• 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
• Clique-connecting forest and stable set polytopes
• Claw-free graphs. VII. Quasi-line graphs
• Facet-inducing web and antiweb inequalities for the graph coloring polytope
• Title not available (Why is that?)
• The stable set polytope of quasi-line graphs
• A construction for non-rank facets of stable set polytopes of webs
• 2-clique-bond of stable set polyhedra
• Clique-circulants and the stable set polytope of fuzzy circular interval graphs
• On dominating set polyhedra of circular interval graphs
• The stable set polytope of icosahedral graphs
• A note on the Chvàtal-Rank of clique family inequalities
• On non-rank facets of stable set polytopes of webs with clique number four
• Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs
• On the facets of the stable set polytope of quasi-line graphs
• On facets of stable set polytopes of claw-free graphs with stability number three
• The stable set problem: clique and nodal inequalities revisited
• Row family inequalities for the set covering polyhedron
• Generalized clique family inequalities for claw-free graphs
• On the facets of stable set polytopes of circular interval graphs

This page was built for publication: Clique family inequalities for the stable set polytope of quasi-line graphs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1414593)