On a composition of independence systems by circuits identification
Euler, Reinhardt; Mahjoub, Ali Ridha (1991), On a composition of independence systems by circuits identification, Journal of Combinatorial Theory , Series B, 53, 2, p. 235-259. http://dx.doi.org/10.1016/0095-8956(91)90076-V
Type
Article accepté pour publication ou publiéDate
1991Nom de la revue
Journal of Combinatorial Theory , Series BVolume
53Numéro
2Éditeur
Elsevier
Pages
235-259
Identifiant publication
Métadonnées
Afficher la notice complèteRésumé (EN)
The composition of general bipartite subgraph respectively acyclic subdigraph independence systems and in particular of their associated polyhedra by the identification of a pair of 3-cycles resp. 2-dicycles together with its implications for an algorithmic treatment has been the central subject of recent papers. We generalize this kind of composition within the framework of independence systems having a certain exchange property with respect to one of their circuits, and extend it to the case of independence systems associated with K3-covers of a graph. We discuss its implications for associated polyhedra, totally dual integral linear systems describing these as well as related optimization problems. As a special result we obtain that the K3-cover problem is polynomially solvable in graphs not contractible to K5−e. Particular attention is also given to independence systems, which are linearly relaxable (with respect to their circuits), i.e., for which the circuit inequalities x(C)≤|C|−1 together with the trivial inequalities O≤xe≤1 are sufficient to describe P(Image ), the convex hull of the incidence vectors of members of Image .Mots-clés
Polyhedra; GraphPublications associées
Affichage des éléments liés par titre et auteur.
-
Fouilhoux, Pierre; Labbé, Martine; Mahjoub, Ali Ridha; Yaman, Hande (2009) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Euler, Reinhardt (1991) Article accepté pour publication ou publié
-
Bendali, Fatiha; Mailfert, Jean; Mahjoub, Ali Ridha (2002) Article accepté pour publication ou publié
-
Barahona, Francisco; Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié
-
Barahona, Francisco; Fonlupt, Jean; Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié