Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Improved approximations of independent dominating set in bounded degree graphs
| |
|
Improved approximations of independent dominating set in bounded degree graphs Paola Alimonti1  and Tiziana Calamoneri2
| (1) |
Dipartimento di Informatica e Sistemistica, Università di Roma  La Sapienza , via Salaria 113, 00198 Roma, Italy |
| (2) |
Dipartimento di Scienze dell'Informazione, Università di Roma La Sapienza, via Salaria 113, 00198 Roma, Italy |
Abstract
We consider the problem of finding an independent dominating set of minimum cardinality in bounded degree and regular graphs. We first give approximate heuristics for MIDS in cubic and at most cubic graphs, based on greedy and local search techniques.
Then, we consider graphs of bounded degree B and B-regular graphs, for B  4. In particular, the greedy phase proposed for at most cubic graphs is extended to any B and iteratively repeated until the degree of the remaining graph is greater than 3. Finally, the algorithm for at most cubic graphs is executed.
Our algorithms achieve approximation ratios:
| – |
1.923 for cubic graphs;
|
| – |
2 for at most cubic and 4-regular graphs;
|
| – |
(B
2–2B+2)(B+1)/B
2+1 for B-regular graphs, B5;
|
| – |
(B
2–B+1)(B+1)/B
2+1 for graphs of bounded degree B4.
|
Keywords Minimum Independent Dominating Set - Approximation Algorithms - Bounded Degree Graphs - Regular Graphs - Cubic Graphs - Greedy - Local Search
Work supported by: the CEE project ALCOM-IT ESPRIT LTR, project no. 20244,  Algorithms and Complexity in Information Technology ; the Italian Project Algoritmi, Modelli di Calcolo e Strutture Informative, Ministero dell'Università e della Ricerca Scientifica e Tecnologica.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|