Fast Algorithms for min independent dominating set

Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis

Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010), Fast Algorithms for min independent dominating set, in Patt-Shamir, Boaz; Ekim, Tinaz, Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings., Springer : Berlin, p. 247-261

View/Open

742A7CC2d01.pdf (148.4Kb)

Type

Communication / Conférence

Date

2010

Conference title

SIROCCO 2010: 17th International Colloquium on Structural Information and Communication Complexity

Conference date

2010-06

Conference city

Sirince

Conference country

Turquie

Book title

Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings.

Book author

Patt-Shamir, Boaz; Ekim, Tinaz

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

6058

Published in

Berlin

ISBN

978-3-642-13283-4

Pages

247-261

Abstract (EN)

We first devise a branching algorithm that computes a minimum independent dominating set with running time O *(20.424n ) and polynomial space. This improves the O *(20.441n ) result by (S. Gaspers and M. Liedloff, A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs, Proc. WG’06). We then study approximation of the problem by moderately exponential algorithms and show that it can be approximated within ratio 1 + ε, for any ε> 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.

Subjects / Keywords

min independent dominating set