Show simple item record

Compositions of Graphs and Polyhedra IV: Acyclic Spanning Subgraphs

dc.contributor.authorBarahona, Francisco
dc.contributor.authorFonlupt, Jean
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2010-04-13T10:11:11Z
dc.date.available2010-04-13T10:11:11Z
dc.date.issued1994
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3956
dc.language.isoenen
dc.subjectPolytopeen
dc.subjectacyclic subgraphsen
dc.subjectcomposition of polyhedraen
dc.subjectPolyhedral combinatoricsen
dc.subject.ddc511en
dc.titleCompositions of Graphs and Polyhedra IV: Acyclic Spanning Subgraphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenGiven a directed graph $D$ that has a two-vertex cut, this paper describes a technique to derive a linear system that defines the acyclic subgraph polytope of $D$ from systems related to the pieces. It also gives a technique to describe facets of this polytope by composition of facets for the pieces. The authors prove that, if the systems for the pieces are totally dual integral (TDI), then the system for $D$ is also. The authors prove that the "cycle inequalities" form a TDI system for any orientation of $K_5$. These results are combined with Lucchesi–Younger theorem and a theorem of Wagner to prove that, for graphs with no $K_{3,3} $ minor, the cycle inequalities characterize the acyclic subgraph polytope and form a TDI system. This shows that, for this class of graphs, the cardinality of a minimum feedback set is equal to the maximum number of arc disjoint cycles. For planar graphs, this is a consequence of the Lucchesi–Younger theorem.en
dc.relation.isversionofjnlnameSIAM Journal on Discrete Mathematics
dc.relation.isversionofjnlvol7en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate1994-05
dc.relation.isversionofjnlpages390-402en
dc.relation.isversionofdoihttp://dx.doi.org/10.1137/S0895480190182691en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSIAMen
dc.subject.ddclabelPrincipes généraux des mathématiquesen


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