Linear Algorithms for \(\omega\)-Medians of Graphs

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.