A degree-based heuristic for strongly connected dominating-absorbent sets in wireless ad-hoc networks
Virtual backbones of asymmetric wireless networks are special sub-nets through which routing can be performed. Such backbone must be as small as possible, and must be able to receive and transmit messages from/to each and every node in the network. The corresponding graph theoretic problem takes a d...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | conferenceObject |
| Published: |
2017
|
| Online Access: | http://hdl.handle.net/10725/5383 http://dx.doi.org/10.1109/INNOVATIONS.2012.6207732 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://ieeexplore.ieee.org/abstract/document/6207732/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Virtual backbones of asymmetric wireless networks are special sub-nets through which routing can be performed. Such backbone must be as small as possible, and must be able to receive and transmit messages from/to each and every node in the network. The corresponding graph theoretic problem takes a directed graph as input and seeks a strongly connected dominating-absorbent set of smallest possible cardinality. We introduce a hybrid heuristic for this problem, in which we combine low-degree vertex elimination and high-degree vertex selection. This simple and efficient method yields very promising experimental results, outperforming known heuristic algorithms. |
|---|