.png){kind=icon}
.png){kind=icon}
Return
Constructing special k-dominating sets using variations on the greedy algorithm
.png){kind=icon}
PRE
AI
DOI：10.1016/j.pmcj.2008.09.009.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper focuses on the efficient selection of a special type of subset of network nodes, which we call a k-SPR set, for the purpose of coordinating the routing of messages through a network. Such a set is a special k-hop-connected k-dominating set that has an additional property that promotes the regular occurrence of routers in all directions. The distributed algorithms introduced here for obtaining a k-SPR set require that each node broadcast at most three messages to its k-hop neighbors. These transmissions can be made asynchronously. The time required to send these messages and the sizes of the resulting sets are compared by means of data collected from simulations. The main contribution is the adaptation of some variations of the distributed greedy algorithms to the problem of generating a small k-SPR set. These variations are much faster than the standard distributed greedy algorithm. Yet, when used with a sensible choice for a certain parameter, our empirical evidence strongly suggests that the resulting set size will generally be very close to the set size for the standard greedy algorithms. (C) 2008 Elsevier B. V. All rights reserved.
Keywords:
Distributed greedy algorithm
Ad hoc network
Routing
Dominating set
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.5
Papers:
1.5K
Citations:
2.2K
