A degree-based heuristic for strongly connected dominating-absorbent sets in wireless ad-hoc networks

C Markarian, Faisal Abu Khzam

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of 2012 International Conference on Innovations in Information Technology, IIT 2012
Place of PublicationAbu Dhabi, Al-Ain, United Arab Emirates
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages200-204
Number of pages5
ISBN (Print)978-1-4673-1100-7
DOIs
Publication statusPublished - 2012
Externally publishedYes
EventInternational Conference on Innovations in Information Technology (IIT 2012) - Abu Dhabi, Al-Ain; United Arab Emirates, Abu Dhabi, Al-Ain, United Arab Emirates
Duration: 1 Jan 2012 → …
Conference number: 2012

Conference

ConferenceInternational Conference on Innovations in Information Technology (IIT 2012)
Abbreviated titleIIT
CountryUnited Arab Emirates
CityAbu Dhabi, Al-Ain
Period1/01/12 → …

Fingerprint Dive into the research topics of 'A degree-based heuristic for strongly connected dominating-absorbent sets in wireless ad-hoc networks'. Together they form a unique fingerprint.

  • Cite this

    Markarian, C., & Abu Khzam, F. (2012). A degree-based heuristic for strongly connected dominating-absorbent sets in wireless ad-hoc networks. In Proceedings of 2012 International Conference on Innovations in Information Technology, IIT 2012 (pp. 200-204). IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/INNOVATIONS.2012.6207732