The plurality strategy on graphs
The Majority Strategy for finding medians of a set of clients on a graph can be relaxed in the following way: if we are at v, then we move to a neighbor w if there are at least as many clients closer to w than to v (thus ignoring the clients at equal distance from v and w). The graphs on which this Plurality Strategy always finds the set of all medians are precisely those for which the set of medians induces always a connected subgraph.
|, , , ,|
|Econometric Institute Research Papers|
|Report / Econometric Institute, Erasmus University Rotterdam|
|Organisation||Erasmus School of Economics|
Balakrishnan, K, Changat, M, & Mulder, H.M. (2006). The plurality strategy on graphs (No. EI 2006-35). Report / Econometric Institute, Erasmus University Rotterdam. Retrieved from http://hdl.handle.net/1765/7976