---
res:
bibo_abstract:
- Dominating set based virtual backbones are used for rou-ting in wireless ad-hoc
networks. Such backbones receive and transmit messages from/to every node in the
network. Existing distributed algorithms only consider undirected graphs, which
model symmetric networks with uniform transmission ranges. We are particularly
interested in the well-established disk graphs, which model asymmetric networks
with non-uniform transmission ranges. The corresponding graph theoretic problem
seeks a strongly connected dominating-absorbent set of minimum cardinality in
a digraph. A subset of nodes in a digraph is a strongly connected dominating-absorbent
set if the subgraph induced by these nodes is strongly connected and each node
in the graph is either in the set or has both an in-neighbor and an out-neighbor
in it. We introduce the first distributed algorithm for this problem in disk graphs.
The algorithm gives an O(k^4) -approximation ratio and has a runtime bound of
O(Diam) where Diam is the diameter of the graph and k denotes the transmission
ratio r_{max}/r_{min} with r_{max} and r_{min} being the maximum and minimum transmission
range, respectively. Moreover, we apply our algorithm on the subgraph of disk
graphs consisting of only bidirectional edges. Our algorithm gives an O(ln k)
-approximation and a runtime bound of O(k^8 log^∗ n) , which, for bounded k ,
is an optimal approximation for the problem, following Lenzen and Wattenhofer’s
Ω(log^∗ n) runtime lower bound for distributed constant approximation in disk
graphs.
bibo_authorlist:
- foaf_Person:
foaf_givenName: Christine
foaf_name: Markarian, Christine
foaf_surname: Markarian
foaf_workInfoHomepage: http://www.librecat.org/personId=37612
- foaf_Person:
foaf_givenName: Friedhelm
foaf_name: Meyer auf der Heide, Friedhelm
foaf_surname: Meyer auf der Heide
foaf_workInfoHomepage: http://www.librecat.org/personId=15523
- foaf_Person:
foaf_givenName: Michael
foaf_name: Schubert, Michael
foaf_surname: Schubert
bibo_doi: 10.1007/978-3-642-45346-5_16
dct_date: 2013^xs_gYear
dct_title: A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent
Sets in Asymmetric Wireless Ad-Hoc Networks@
...