Thumbnail

Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the $\mathcal{G}(n,p)$ random model

Bourgeois, N.; Catellier, Rémi; Denat, T.; Paschos, Vangelis (2015), Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the $\mathcal{G}(n,p)$ random model. https://basepub.dauphine.fr/handle/123456789/17931

View/Open
Type
Document de travail / Working paper
Date
2015
Publisher
Cahier du LAMSADE
Series title
Cahier du LAMSADE
Published in
Paris
Metadata
Show full item record
Author(s)
Bourgeois, N.

Catellier, Rémi

Denat, T.

Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We 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.
Subjects / Keywords
Computational Complexity