Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949557 | Discrete Applied Mathematics | 2017 | 10 Pages |
Abstract
A median (antimedian) of a profile of vertices on a graph G is a vertex that minimizes (maximizes) the sum of the distances to the elements in the profile. The median (antimedian) function has as output the set of medians (antimedians) of a profile. It is one of the basic models for the location of a desirable (obnoxious) facility in a network. The median function is well studied. For instance it has been characterized axiomatically by three simple axioms on median graphs. The median function behaves nicely on many classes of graphs. In contrast the antimedian function does not have a nice behavior on most classes. So a nice axiomatic characterization may not be expected. In this paper an axiomatic characterization is obtained for the median and antimedian function on complete graphs minus a matching.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Manoj Changat, Divya Sindhu Lekha, Shilpa Mohandas, Henry Martyn Mulder, Ajitha R. Subhamathi,