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