Solving the Absolute 1-Center Problem in the Quickest Path Case

An undirected graph G = (V, A) by a set V of n nodes, a set A of m edges, and a set D ⊆ V consists of h demand nodes are given. Peeters (Eur J Oper Res 104:299–309, 1998) presented the absolute 1-center problem, which finds a point x placed on nodes or edges of the graph G with the property that the cost distance from the most expensive demand node to x is as cheap as possible. In the absolute 1-center problem, the distance between two nodes is computed through a shortest path between them. This paper expands the idea of Peeters (1998) and presents a new version of the absolute 1-center problem, which is called the absolute quickest 1-center problem. A value σ is given, and the problem finds a point x∗ placed on nodes or edges of the graph G with the property that the transmission time of the quickest path to send σ units of data from the farthest demand node to x∗ is the minimum value. We presented an O(r |D|(m +nlog n)) time algorithm to solve the absolute quickest 1-center problem, where r is the number of distinct capacity values.