• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Fast algorithms for min independent dominating set

Thumbnail
Date
2013
Link to item file
https://arxiv.org/abs/0905.1993v1
Dewey
Recherche opérationnelle
Sujet
Approximation algorithms; min independent dominating set; Exact algorithms; Exponential algorithms
Journal issue
Discrete Applied Mathematics
Volume
161
Number
4-5
Publication date
2013
Article pages
558-572
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2012.01.003
Conference name
Seventh International Conference on Graphs and Optimization 2010
Conference date
06-2010
Conference city
Ovronnaz
Conference country
Switzerland
URI
https://basepub.dauphine.fr/handle/123456789/11465
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bourgeois, Nicolas
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Della Croce, Federico
Escoffier, Bruno
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
Communication / Conférence
Item number of pages
558-572
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.