Show simple item record

dc.contributor.authorHansen, Pierre
dc.contributor.authorJaumard, Brigitte
dc.contributor.authorMinoux, Michel
dc.date.accessioned2014-08-28T12:39:58Z
dc.date.available2014-08-28T12:39:58Z
dc.date.issued1986
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/13865
dc.language.isoenen
dc.subjectBoolean Inequalitiesen
dc.subjectImplication Graphen
dc.subjectDepth-First Searchen
dc.subjectStrongly Connected Componentsen
dc.subjectTransitive Closureen
dc.subject0–1 Programmingen
dc.subject.ddc005en
dc.titleA linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalitiesen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenConsider a set R of m binary relations on a set of n boolean variables. R may imply a contradiction, the fixation of some variables at 0 or at 1 and/or the identification of some pairs of variables in direct or complemented form. An O(n) expected-time algorithm is given for the derivation of all such logical conclusions. Computational experiments with problems involving up to 2000 variables are reported on. The proposed algorithm is more than 100 times faster than previous methods when n ≥ 100.en
dc.relation.isversionofjnlnameMathematical Programming
dc.relation.isversionofjnlvol34en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate1986
dc.relation.isversionofjnlpages223-231en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/BF01580586en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen


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