• 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

Fast algorithms for min independent dominating set

Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2013), Fast algorithms for min independent dominating set, Seventh International Conference on Graphs and Optimization 2010, 2010-06, Ovronnaz, Switzerland

Type
Communication / Conférence
External document link
https://arxiv.org/abs/0905.1993v1
Date
2013
Conference title
Seventh International Conference on Graphs and Optimization 2010
Conference date
2010-06
Conference city
Ovronnaz
Conference country
Switzerland
Journal name
Discrete Applied Mathematics
Volume
161
Number
4-5
Publisher
Elsevier
Pages
558-572
558-572
Publication identifier
10.1016/j.dam.2012.01.003
Metadata
Show full item record
Author(s)
Bourgeois, Nicolas
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Della Croce, Federico

Escoffier, Bruno
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We first devise a branching algorithm that computes a minimum independent dominating set with running time O∗(1.3351n)=O∗(20.417n)O∗(1.3351n)=O∗(20.417n) and polynomial space. This improves upon the best state of the art algorithms for this problem. We then study approximation of the problem by moderately exponential time algorithms and show that it can be approximated within ratio 1+ϵ1+ϵ, for any ϵ>0ϵ>0, in a time smaller than the one of exact computation and exponentially decreasing with ϵϵ. We also propose approximation algorithms with better running times for ratios greater than 3 in general graphs and give improved moderately exponential time approximation results in triangle-free and bipartite graphs. These latter results are based upon a new bound on the number of maximal independent sets of a given size in these graphs, which is a result interesting per se.
Subjects / Keywords
Approximation algorithms; min independent dominating set; Exact algorithms; Exponential algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    Fast Algorithms for min independent dominating set 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010) Communication / Conférence
  • Thumbnail
    Algorithms for dominating clique problems 
    Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2012) Article accepté pour publication ou publié
  • Thumbnail
    Exact Algorithms for Dominating Clique Problems 
    Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2009) 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
  • Thumbnail
    Fast Algorithms for max independent set 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis; Van Rooij, Johan (2012) Article accepté pour publication ou publié
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