Title :
Finding a small set of high degree nodes in time-varying graphs
Author :
Antony, Mariamma ; Gupta, Arpan
Author_Institution :
Dept. of Comput. Sci. & Eng., Indian Inst. of Technol. Kharagpur, Kharagpur, India
Abstract :
A time-varying graph (TVG) can model useful practical scenarios such as intermittent contact between nodes. High degree nodes in such networks can act as central nodes for efficient implementation of different applications such as information dissemination. In this paper, we propose a distributed algorithm for finding a low cardinality set of high degree nodes in a time-varying graph. The algorithm efficiently exploits the overlap in coverage between nodes to reduce the size of the set and finds a small subset of all high degree nodes in the network while still maintaining almost the same coverage as the set of all high degree nodes. It also finds temporal paths from all nodes to the high degree nodes found which can be used for routing information to the nodes.
Keywords :
distributed algorithms; graph theory; mobile computing; set theory; TVG; distributed algorithm; high degree nodes; information dissemination; information routing; intermittent contact; mobile wireless devices; size reduction; temporal paths; time-varying graphs; Absorption; Broadcasting; Delays; Distributed algorithms; Indexes; Mobile communication; Routing;
Conference_Titel :
World of Wireless, Mobile and Multimedia Networks (WoWMoM), 2014 IEEE 15th International Symposium on a
Conference_Location :
Sydney, NSW
DOI :
10.1109/WoWMoM.2014.6918918