http://www.cnr.it/ontology/cnr/individuo/prodotto/ID7427
Gear Composition of stable set polytopes and G-perfection (Articolo in rivista)
- Type
- Label
- Gear Composition of stable set polytopes and G-perfection (Articolo in rivista) (literal)
- Anno
- 2009-01-01T00:00:00+01:00 (literal)
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
- 10.1287/moor.1090.0407 (literal)
- Alternative label
Galluccio, A.; Gentile, C.; Ventura , P. (2009)
Gear Composition of stable set polytopes and G-perfection
in Mathematics of operations research
(literal)
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
- Galluccio, A.; Gentile, C.; Ventura , P. (literal)
- Pagina inizio
- Pagina fine
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
- Rivista
- Note
- ISI Web of Science (WOS) (literal)
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
- Istituto analisi dei sistemi ed informatica \"Antonio Ruberti\" (literal)
- Titolo
- Gear Composition of stable set polytopes and G-perfection (literal)
- Abstract
- Graphs obtained by applying the gear composition to a given graph H
are called geared graphs. We show how a linear description of the stable set polytope STAB(G) of
a geared graph G can be obtained by extending the linear inequalities defining STAB(H) and STAB(H^e),
where H^e is the the graph obtained from H by subdividing the edge e.
We also introduce the class of G-perfect graphs, i.e., graphs whose stable
set polytope is described by: nonnegativity inequalities, rank inequalities, lifted 5-wheel inequalities,
and some special inequalities called geared inequalities and g-lifted inequalities.
We prove that graphs obtained by repeated applications of the gear composition
to a given graph H are G-perfect, provided that any graph obtained from H by
subdividing a subset of its simplicial edges is G-perfect.
In particular, we show that a large subclass of claw-free graphs is G-perfect, thus
providing a partial answer to the well-known problem of finding a defining linear system for the
stable set polytope of claw-free graphs. (literal)
- Prodotto di
- Autore CNR
Incoming links:
- Autore CNR di
- Prodotto
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi