Linear Algorithms for $\omega$-Medians of Graphs

Abstract

Suppose $G=(V,E)$ is a graph in which every vertex $v$ has a non-negative real number $\omega (v)$ as its weight. The $\omega$-distance sum of $v$ is $D_{G,\omega }(v)=\sum _{u\in V}d(v,u)\omega (u).$ The $\omega$-median $M_{\omega }(G)$ of $G$ is the set of all vertices $v$ with minimum $\omega$-distance sum $D_{G,\omega }(v)$. This paper gives linear-time algorithms for computing the $\omega$-medians of interval graphs and block graphs.