### Abstract

We consider the problem of dominating set-based virtual backbone used for routing in asymmetric wireless ad-hoc networks. These networks have non-uniform transmission ranges and are modeled using the well-established disk graphs. 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. Distributed algorithms for this problem are of practical significance due to the dynamic nature of ad-hoc networks. We present a first distributed approximation algorithm, with a constant approximation factor and O(Diam) running time, where Diam is the diameter of the graph. Moreover we present a simple heuristic algorithm and conduct an extensive simulation study showing that our heuristic outperforms previously known approaches for the problem.

Original language | English |
---|---|

Pages (from-to) | 1673-1689 |

Number of pages | 17 |

Journal | Theory of Computing Systems |

Volume | 62 |

Issue number | 8 |

Early online date | 10 Jan 2018 |

Publication status | Published - Nov 2018 |

## Fingerprint Dive into the research topics of 'Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-Hoc Networks'. Together they form a unique fingerprint.

## Cite this

Abu Khzam, F., Markarian, C., Meyer auf der Heide, F., & Schubert, M. (2018). Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-Hoc Networks.

*Theory of Computing Systems*,*62*(8), 1673-1689.