Computing median and antimedian sets in median graphs

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

The median function on graphs with bounded profiles

The median of a profile = (u1, . . . , uk ) of vertices of a graph G is the set of vertices x that minimize the sum of distances from x to the vertices of . It is shown that for profiles with diameter the median set can be computed within an isometric subgraph of G that contains a vertex x of and the r -ball around x, where r > 2 − 1 − 2 /| |. The median index of a graph and r -joins of graphs are introduced and it is shown that r -joins preserve the property of having a large median index. Consensus strategies are also briefly discussed on a graph with bounded profiles.