A sifting-edges algorithm for accelerating the computation of absolute 1-center in graphs

Abstract

Let $G = (V, E, w)$ be an undirected connected edge-weighted graph, where V is the n-vertices set, E is the m-edges set, and $w: E \rightarrow \mathbb {R}^+$ is a positive edge-weight function. Given $G = (V, E, w)$, a subset $X \subseteq V$ of p terminals, and a subset $F \subseteq E$ of candidate edges, the Absolute 1-Center Problem (A1CP) aims to find a point on some edge in F to minimize the distance from it to X. This paper revisits this classic and polynomial-time solvable problem from a novel perspective and finds some new and nontrivial properties of it, with the highlight of establishing the relationship between the A1CP and the saddle point of distance matrix. In this paper, we prove that an absolute 1-center is just a vertex 1-center if the all-pairs shortest paths distance matrix from the vertices covered by the candidate edges in F to X has a (global) saddle point. Furthermore, we define the local saddle point of edge and demonstrate that we can sift the candidate edge having a local saddle point. By incorporating the method of sifting edges into the framework of the well-known Kariv and Hakimi’s algorithm, we develop an $O(m + p m^*+ n p \log p)$-time algorithm for A1CP, where $m^*$ is the number of the remaining candidate edges. Specifically, it takes $O(m^*n + n^2 \log n)$ time to apply our algorithm to the classic A1CP when the distance matrix is known and $O(m n + n^2 \log n)$ time when the distance matrix is unknown, which are smaller than $O(mn + n^2 \log n)$ and $O(mn + n^3)$ of Kariv and Hakimi’s algorithm, respectively.