Show simple item record

dc.contributor.authorBourgeois, N.*
dc.contributor.authorCatellier, Rémi*
dc.contributor.authorDenat, T.*
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2018-09-03T14:02:29Z
dc.date.available2018-09-03T14:02:29Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/17931
dc.language.isoenen
dc.subjectComputational Complexity
dc.subject.ddc519en
dc.titleAverage-case complexity of a branch-and-bound algorithm for maximum independent set, under the $\mathcal{G}(n,p)$ random model
dc.typeDocument de travail / Working paper
dc.description.abstractenWe study average-case complexity of branch-and-bound for maximum independent set in random graphs under the $\mathcal{G}(n,p)$ distribution. In this model every pair $(u,v)$ of vertices belongs to $E$ with probability $p$ independently on the existence of any other edge. We make a precise case analysis, providing phase transitions between subexponential and exponential complexities depending on the probability $p$ of the random model.
dc.publisher.nameCahier du LAMSADE
dc.publisher.cityParis
dc.relation.ispartofseriestitleCahier du LAMSADE
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.identifier.citationdate2015
dc.description.ssrncandidatenon
dc.description.halcandidatenon
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2020-05-11T10:15:04Z
hal.person.labIds*
hal.person.labIds*
hal.person.labIds*
hal.person.labIds989*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record