|
|
|
|
|
|
by Schoolmeister
2136 days ago
|
|
|
That's actually an NP-complete problem, called the Dominating Set problem[0]. One application of this problem is used in OLSR[1], a routing protocol used in Mobile Ad-Hoc Networks (MANET). To see how it is useful for MANETs, you can look at the problem in a different, but equivalent, way. Namely, try to find the smallest subset D of nodes (puzzle pieces), such that every two nodes that are not in D are connected to each other through a node in D. In the case of MANETs, these nodes are wireless stations. The nodes in the Domating Set are chosen to relay broadcasting messages for their neighbours. This way congestion on the medium is reduced but every node can still send and receive broadcasts. [0] https://en.wikipedia.org/wiki/Dominating_set [1] https://en.wikipedia.org/wiki/Optimized_Link_State_Routing_P... |
|
|