Book chapter
Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp.312-325
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2009
DOI: 10.1007/978-3-642-03685-9_24
Abstract
We prove a new structural property regarding the “skyline” of uniform radius disks and use this to derive a number of new sequential and distributed approximation algorithms for well-known optimization problems on unit disk graphs (UDGs). Specifically, the paper presents new approximation algorithms for two problems: domatic partition and weighted minimum dominating set (WMDS) on UDGs, both of which are of significant interest to the distributed computing community because of applications to energy conservation in wireless networks. Using the aforementioned skyline property, we derive the first constant-factor approximation algorithm for the domatic partition problem on UDGs. Prior to our work, the best approximation factor for this problem was O(logn), obtained by simply using the approximation algorithm for general graphs. From the domatic partition algorithm, we derive a new and simpler constant-factor approximation for WMDS on UDGs. Because of “locality” properties that our algorithms possess, both algorithms have relatively simple constant-round distributed implementations in the \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal{LOCAL}$\end{document} model, where there is no bound on the message size. In addition, we obtain O(log2n)-round distributed implementations of these algorithms in the \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal{CONGEST}$\end{document} model, where message sizes are bounded above by O(logn) bits per message.
Details
- Title: Subtitle
- Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
- Creators
- Saurav Pandit - University of IowaSriram V. Pemmaraju - University of IowaKasturi Varadarajan - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp.312-325
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-642-03685-9_24
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2009
- Academic Unit
- Computer Science
- Record Identifier
- 9984259500302771
Metrics
5 Record Views