Show simple item record

dc.contributor.authorBarahona, Francisco
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2010-04-13T10:04:23Z
dc.date.available2010-04-13T10:04:23Z
dc.date.issued1994
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3954
dc.language.isoenen
dc.subjectacyclic subgraphsen
dc.subjectcompact systemsen
dc.subjectbalanced subgraphsen
dc.subjectcomposition of polyhedraen
dc.subjectPolyhedral combinatoricsen
dc.subject.ddc511en
dc.titleComposition of graphs and polyhedra I : Balanced induced subgraphs and acyclic subgraphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenLet $P( G )$ be the balanced induced subgraph polytope of $G$. If $G$ has a two-node cutset, then $G$ decomposes into $G_1 $ and $G_2$. It is shown that $P( G )$ can be obtained as a projection of a polytope defined by a system of inequalities that decomposes into two pieces associated with $G_1 $ and $G_2$. The problem max $cx,x \in P( G )$ is decomposed in the same way. This is applied to series-parallel graphs to show that, in this case, $P( G )$ is a projection of a polytope defined by a system with $O( n )$ inequalities and $O( n )$ variables, where $n$ is the number of nodes in $G$. Also for this class of graphs, an algorithm is given that finds a maximum weighted balanced induced subgraph in $O( n\log n )$ time. This approach is also used to obtain composition of facets of $P( G )$. Analogous results are presented for acyclic induced subgraphs.en
dc.relation.isversionofjnlnameSIAM Journal on Discrete Mathematics
dc.relation.isversionofjnlvol7en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate1994-05
dc.relation.isversionofjnlpages344-358en
dc.relation.isversionofdoihttp://dx.doi.org/10.1137/S0895480190182666en
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