• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
1505.04969.pdf (224.3Kb)
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

Related items

Showing items related by title and author.

  • Thumbnail
    A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem 
    Afif, Mohamed; Likas, Aris; Paschos, Vangelis (1995) Article accepté pour publication ou publié
  • Thumbnail
    Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537^n) 
    Van Rooij, Johan; Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010) Communication / Conférence
  • Thumbnail
    Fast algorithms for Max Independant Set in graphs of small average degree 
    van Rooij, Johan; Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2008) Document de travail / Working paper
  • Thumbnail
    Average case analysis of a greedy algorithm for the minimum hitting set problem 
    Fernandez de la Vega, Wenceslas; Paschos, Vangelis; Saad, Rachid (1992) Communication / Conférence
  • Thumbnail
    A Bottom-Up Method and Fast Algorithms for max independent set 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo