LAUSR

An undirected graph $$G=(V,A)$$ G = ( V , A ) by a set V of n nodes, a set A of m edges, and a set $$D\subseteq V$$ 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 $$\sigma $$ σ is given, and the problem finds a point $$x^*$$ x ∗ placed on nodes or edges of the graph G with the property that the transmission time of the quickest path to send $$\sigma $$ σ units of data from the farthest demand node to $$x^*$$ x ∗ is the minimum value. We presented an $$O(r|D|(m+n\mathrm{{log}}\ n))$$ O ( r | D | ( m + n log n ) ) time algorithm to solve the absolute quickest 1-center problem, where r is the number of distinct capacity values.