The plurality strategy on graphs
2006-09-15
Research Paper
This publication is part of collection
| Related Files |
|---|
View PDF Version
(ei2006-35.pdf, 0.1MB) |
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.
Keywords
Automatically Extracted Terms
- graph
- vertex
- strategy
- function
- profile
- plurality strategy
- weight
- vertice
- plurality
- majority
- weight function
- median
- majority strategy
- neighbor
- client
- weight functions f
- vertex v
- lemma
- ascent hill
- weight function f
