Show simple item record

On a composition of independence systems by circuits identification

dc.contributor.authorEuler, Reinhardt
HAL ID: 745514
ORCID: 0000-0002-4294-286X
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2010-03-16T08:33:25Z
dc.date.available2010-03-16T08:33:25Z
dc.date.issued1991
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3696
dc.language.isoenen
dc.subjectPolyhedraen
dc.subjectGraphen
dc.subject.ddc003en
dc.titleOn a composition of independence systems by circuits identificationen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe 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 .en
dc.relation.isversionofjnlnameJournal of Combinatorial Theory , Series B
dc.relation.isversionofjnlvol53en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate1991-11
dc.relation.isversionofjnlpages235-259en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/0095-8956(91)90076-Ven
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record