dc.contributor.author Barahona, Francisco dc.contributor.author Mahjoub, Ali Ridha dc.date.accessioned 2010-04-13T10:04:23Z dc.date.available 2010-04-13T10:04:23Z dc.date.issued 1994 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/3954 dc.language.iso en en dc.subject acyclic subgraphs en dc.subject compact systems en dc.subject balanced subgraphs en dc.subject composition of polyhedra en dc.subject Polyhedral combinatorics en dc.subject.ddc 511 en dc.title Composition of graphs and polyhedra I : Balanced induced subgraphs and acyclic subgraphs en dc.type Article accepté pour publication ou publié dc.description.abstracten Let $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.isversionofjnlname SIAM Journal on Discrete Mathematics dc.relation.isversionofjnlvol 7 en dc.relation.isversionofjnlissue 3 en dc.relation.isversionofjnldate 1994-05 dc.relation.isversionofjnlpages 344-358 en dc.relation.isversionofdoi http://dx.doi.org/10.1137/S0895480190182666 en dc.description.sponsorshipprivate oui en dc.relation.isversionofjnlpublisher SIAM en dc.subject.ddclabel Principes généraux des mathématiques en
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.