A low degree vertex elimination with high degree vertex selection heuristic for strongly connected dominating and absorbent sets in wireless Ad-Hoc networks. (c2011)

Abstract

In the Strongly Connected Dominating-Absorbent Set problem (SCDAS), we are given a directed graph and asked to find a subset D of vertices such that the subgraph induced by D is strongly connected and every vertex not in D has both an in-neighbor and an out-neighbor in D. SCDAS received attention recently because “small” strongly connected dominating-absorbent sets serve as “efficient” virtual backbones in asymmetric wireless networks. This thesis studies the Minimum SCDAS problem, which seeks a smallest SCDAS in a given digraph. We introduce a new heuristic approach based on a hybrid of low-degree vertex elimination and high-degree vertex selection. Experimental results show that our approach outperforms all previously known algorithms for the SCDAS problem.