The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are G-perfect (Articolo in rivista)

Type

• Articolo in rivista (Classe)
• Prodotto della ricerca (Classe)

Label

• The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are G-perfect (Articolo in rivista) (literal)

Anno

• 2014-01-01T00:00:00+01:00 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi

• 10.1016/j.jctb.2014.02.009 (literal)

Alternative label

• Galluccio, A.; Gentile, C.; Ventura, P. (2014)
  The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are G-perfect
  in Journal of combinatorial theory. Series B (Print)
  (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

• Galluccio, A.; Gentile, C.; Ventura, P. (literal)

Pagina inizio

• 1 (literal)

Pagina fine

• 28 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

• 108 (literal)

Rivista

• Journal of combinatorial theory. Series B (Rivista)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali

• 28 (literal)

Note

• ISI Web of Science (WOS) (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

• Consiglio Nazionale delle Ricerche (CNR) (literal)

Titolo

• The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are G-perfect (literal)

Abstract

• In [6], Edmonds provided the first complete description of the polyhedron associated with a combinatorial optimization problem: the matching polytope. As the matching problem is equivalent to the stable set problem on line graphs, many researchers tried to generalize Edmonds' result by considering the stable set problem on a superclass of line graphs: the claw-free graphs. However, as testified also by Grotschel, Lovasz, and Schrijver [14], \"in spite of considerable efforts, no decent system of inequalities describing STAB(G) for claw-free graphs is known\". Here, we provide an explicit linear description of the stable set polytope of claw-free graphs with stability number at least four and with no 1-join. (literal)

Prodotto di

• Controllo e Ottimizzazione di Sistemi Complessi (ICT.P11.005.001) (Modulo)
• Istituto di analisi dei sistemi ed informatica \"Antonio Ruberti\" (IASI) (Istituto)

Autore CNR

• ANNA GALLUCCIO (Persona)
• CLAUDIO GENTILE (Persona)
• PAOLO VENTURA (Persona)

Insieme di parole chiave

• Parole chiave di "The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are G-perfect" (Insieme di parole chiave)

Incoming links:

Autore CNR di

• CLAUDIO GENTILE (Persona)
• ANNA GALLUCCIO (Persona)
• PAOLO VENTURA (Persona)

Prodotto

• Istituto di analisi dei sistemi ed informatica \"Antonio Ruberti\" (IASI) (Istituto)
• Controllo e Ottimizzazione di Sistemi Complessi (ICT.P11.005.001) (Modulo)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi

• Journal of combinatorial theory. Series B (Rivista)

Insieme di parole chiave di

• Parole chiave di "The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are G-perfect" (Insieme di parole chiave)