• 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

Exact Algorithms for Dominating Clique Problems

Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2009), Exact Algorithms for Dominating Clique Problems, in Ibarra, Oscar H.; Du, Ding-Zhu; Dong, Ying Fei, Algorithms and Computation 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, Springer : Berlin, p. 4-13

View/Open
cahierLamsade285.pdf (376.4Kb)
Type
Communication / Conférence
Date
2009
Conference title
ISAAC 2009 20th International Symposium on Algorithms and Computation
Conference date
2009-12
Conference city
Hawaï
Conference country
États-Unis
Book title
Algorithms and Computation 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings
Book author
Ibarra, Oscar H.; Du, Ding-Zhu; Dong, Ying Fei
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
5878
Published in
Berlin
ISBN
978-3-642-10630-9
Pages
4-13
Publication identifier
http://dx.doi.org/10.1007/978-3-642-10631-6_3
Metadata
Show full item record
Author(s)
Bourgeois, Nicolas
Della Croce, Federico
Escoffier, Bruno
Paschos, Vangelis
Abstract (EN)
We handle in this paper three dominating clique problems, namely, the decision problem itself when one asks if there exists a dominating clique in a graph G and two optimization versions where one asks for a maximum- and a minimum-size dominating clique, if any. For the three problems we propose optimal algorithms with provably worst-case upper bounds improving existing ones by (D. Kratsch and M. Liedloff, An exact algorithm for the minimum dominating clique problem, Theoretical Computer Science 385(1-3), pp. 226–240, 2007). We then settle all the three problems in sparse and dense graphs also providing improved upper running time bounds.
Subjects / Keywords
Optimal Algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    Algorithms for dominating clique problems 
    Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2012) Article accepté pour publication ou publié
  • Thumbnail
    Fast algorithms for min independent dominating set 
    Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2013) Communication / Conférence
  • Thumbnail
    Worst-case complexity of exact algorithms for NP-hard problems 
    Della Croce, Federico; Escoffier, Bruno; Kaminski, Marcin; Paschos, Vangelis (2008) Chapitre d'ouvrage
  • Thumbnail
    An Introduction to Exponential Time Exact Algorithms for Solving NP-hard Problems 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2011) Chapitre d'ouvrage
  • Thumbnail
    Fast Algorithms for min independent dominating 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