Average-case complexity of a branch-and-bound algorithm for max independent set under the G(n,p) random model

Thumbnail
Ouvrir
Date
2015
Titre de la collection
Cahier de recherche CEREMADE
Indexation documentaire
Probabilités et mathématiques appliquées
Subject
Computational Complexity
URI
https://basepub.dauphine.fr/handle/123456789/17931
Collections
Métadonnées
Afficher la notice complète
Auteur
Bourgeois, Nicolas
92163 Statistique, Analyse et Modélisation Multidisciplinaire (SAmos-Marin Mersenne) [SAMM]
Catellier, Rémi
75 Institut de Recherche Mathématique de Rennes [IRMAR]
60 CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Denat, Tom
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Document de travail / Working paper
Résumé en anglais
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.