Polytope des independants d'un graphe série-parallèle

DOI10.1016/0012-365X(79)90160-2zbMath0449.05065MaRDI QIDQ1147168

Jean-Pierre Uhry, Mouloud Boulala

Publication date: 1979

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

zbMATH Keywords

Chvatal's conjectureLP-dualityserie parallel graphs

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items (25)

Relaxations of vertex packing ⋮ A solvable case of quadratic 0-1 programming ⋮ Arborescence polytopes for series-parallel graphs ⋮ Matrices with the Edmonds-Johnson property ⋮ On the stable set polytope of a series-parallel graph ⋮ Fractional and integral colourings ⋮ The Boolean quadratic polytope: Some characteristics, facets and relatives ⋮ Facets of the balanced (acyclic) induced subgraph polytope ⋮ On cutting-plane proofs in combinatorial optimization ⋮ Complementation in T-perfect graphs ⋮ $t$-Perfection in $P_5$-Free Graphs ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ On claw-free \(t\)-perfect graphs ⋮ Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs ⋮ A solvable class of quadratic 0-1 programming ⋮ A min-max relation for stable sets in graphs with no odd-\(K_ 4\) ⋮ Extended formulations for vertex cover ⋮ Computing the clique number of \(a\)-perfect graphs in polynomial time ⋮ Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time ⋮ Characterising claw-free t-perfect graphs ⋮ Graph imperfection. I ⋮ A class of h-perfect graphs ⋮ The maximum clique problem ⋮ \(K_ i\)-covers. I: Complexity and polytopes ⋮ The Steiner tree polytope and related polyhedra

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Topology of series-parallel networks
• Edmonds polytopes and a hierarchy of combinatorial problems
• Vertex packings: Structural properties and algorithms
• Further facet generating procedures for vertex packing polytopes
• Properties of vertex packing and independence system polyhedra
• On the facial structure of set packing polyhedra
• The Strong Perfect Graph Conjecture for Planar Graphs

This page was built for publication: Polytope des independants d'un graphe série-parallèle