An antimedian of a pro le = (x1; x2; : : : ; xk) of vertices of a graph G is a
vertex maximizing the sum of the distances to the elements of the pro le. The
antimedian function is de ned on the set of all pro les on G and has as output
the set of antimedians of a pro le. It is a typical location function for nding a
location for an obnoxious facility. The `converse' of the antimedian function is the
median function, where the distance sum is minimized. 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 such a characterization is obtained for the two classes of graphs on which
the antimedian is well-behaved: paths and hypercubes.
The median (antimedian) set of a profile π = (u1, . . . , uk) of vertices of a
graphG is the set of vertices x that minimize (maximize) the remoteness i d(x,ui ).
Two algorithms for median graphs G of complexity O(nidim(G)) are designed,
where n is the order and idim(G) the isometric dimension of G. The first algorithm computes median sets of profiles and will be in practice often faster than the other
algorithm which in addition computes antimedian sets and remoteness functions and
works in all partial cubes
Description:
Algorithmica (2010) 57: 207–216
DOI 10.1007/s00453-008-9200-4