Lovász-Schrijver PSD-Operator on Claw-Free Graphs

DOI10.1007/978-3-319-45587-7_6zbMath1432.52020arXiv1612.02670OpenAlexW2514398482MaRDI QIDQ2835662

Silvia M. Bianchi, Mariana S. Escalante, Annegret K. Wagler, Graciela L. Nasini

Publication date: 30 November 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1612.02670

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Structural characterization of families of graphs (05C75)

Related Items (2)

Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs ⋮ On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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 claw-free graphs with stability number at least four. II. Striped graphs are \(\mathcal{G}\)-perfect
• The strong perfect graph theorem
• Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture
• The stable set polytope of quasi-line graphs
• On facets of stable set polytopes of claw-free graphs with stability number 3
• Gear composition and the stable set polytope
• Characterizing and bounding the imperfection ratio for some classes of graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• The ellipsoid method and its consequences in combinatorial optimization
• On stable set polyhedra for K//(1,3)free graphs
• Geometric algorithms and combinatorial optimization
• Near-perfect matrices
• On certain polytopes associated with graphs
• The stable set problem and the lift-and-project ranks of graphs
• On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs
• Antiwebs are rank-perfect
• Applying Lehman's theorems to packing problems
• Almost all webs are not rank-perfect
• Near-perfect graphs with polyhedral
• Characterizing N+-perfect line graphs
• Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Lovász-Schrijver PSD-Operator on Claw-Free Graphs