• 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 - No thumbnail

An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs

Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2008), An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs, in Grohe, Martin; Niedermeier, Rolf, Parameterized and Exact Computation Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008, Proceedings, Springer : Berlin, p. 55-65. http://dx.doi.org/10.1007/978-3-540-79723-4_7

Type
Communication / Conférence
External document link
http://hal.archives-ouvertes.fr/hal-00203163/en/
Date
2008
Conference title
Third International Workshop on Parameterized and Exact Computation Parameterized and Exact Computation (IWPEC 2008)
Conference date
2008-05
Conference city
Victoria
Conference country
Canada
Book title
Parameterized and Exact Computation Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008, Proceedings
Book author
Grohe, Martin; Niedermeier, Rolf
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
5018
Published in
Berlin
ISBN
978-3-540-79722-7
Number of pages
227
Pages
55-65
Publication identifier
http://dx.doi.org/10.1007/978-3-540-79723-4_7
Metadata
Show full item record
Author(s)
Bourgeois, Nicolas
Escoffier, Bruno
Paschos, Vangelis
Abstract (EN)
We present an O *(1.0977 n ) search-tree based exact algorithm for max independent set in graphs with maximum degree 3. It can be easily seen that this algorithm also works in graphs with average degree 3.
Subjects / Keywords
graphs; max independent set

Related items

Showing items related by title and author.

  • 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
    A Bottom-Up Method and Fast Algorithms for max independent set 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010) Communication / Conférence
  • Thumbnail
    Fast Algorithms for max independent set 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis; Van Rooij, Johan (2012) Article accepté pour publication ou publié
  • Thumbnail
    Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) 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
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