Minimizing the expense transmission time from the source node to demand nodes

An undirected graph $$G=(V,A)$$ G = ( V , A ) by a set V of n nodes, a set A of m edges, and two sets $$S,\ D\subseteq V$$ S , D ⊆ V consists of source and demand nodes are given. This paper presents two new versions of location problems which are called the $$f(\sigma )$$ f ( σ ) -location and $$g(\sigma )$$ g ( σ ) -location problems. We define an $$f(\sigma )$$ f ( σ ) -location of the network N as a node $$s\in S$$ s ∈ S with the property that the maximum expense transmission time from the node s to the destinations of D is as cheap as possible. The $$f(\sigma )$$ f ( σ ) -location problem divides the range $$(0,\infty )$$ ( 0 , ∞ ) into intervals $$\displaystyle \cup _{i}{(a_i,b_i)}$$ ∪ i ( a i , b i ) and finds a source $$s_i\in S$$ s i ∈ S , for each interval $$(a_i,b_i)$$ ( a i , b i ) , such that $$s_i$$ s i is a $$f(\sigma )$$ f ( σ ) -location for each $$\sigma \in (a_i,b_i)$$ σ ∈ ( a i , b i ) . Also, define a $$g(\sigma )$$ g ( σ ) -location as a node s of S with the property that the sum of expense transmission times from the node s to all destinations of D is as cheap as possible. The $$g(\sigma )$$ g ( σ ) -location problem divides the range $$(0,\infty )$$ ( 0 , ∞ ) into intervals $$\displaystyle \cup _{i}{(a_i,b_i)}$$ ∪ i ( a i , b i ) and finds a source $$s_i\in S$$ s i ∈ S , for each interval $$(a_i,b_i)$$ ( a i , b i ) , such that $$s_i$$ s i is a $$g(\sigma )$$ g ( σ ) -location for each $$\sigma \in (a_i,b_i)$$ σ ∈ ( a i , b i ) . This paper presents two strongly polynomial time algorithms to solve $$f(\sigma )$$ f ( σ ) -location and $$g(\sigma )$$ g ( σ ) -location problems.