|
چکیده
|
An undirected graph G = (V, A) by a set V of n nodes, a set A of m edges, and two sets 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 (σ )-location and g(σ )- location problems. We define an f (σ )-location of the network N as a node 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 (σ )-location problem divides the range (0,∞) into intervals ∪i (ai , bi ) and finds a source si ∈ S, for each interval (ai , bi ), such that si is a f (σ )-location for each σ ∈ (ai , bi ). Also, define a 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(σ )-location problem divides the range (0,∞) into intervals ∪i (ai , bi ) and finds a source si ∈ S, for each interval (ai , bi ), such that si is a g(σ )-location for each σ ∈ (ai , bi ). This paper presents two strongly polynomial time algorithms to solve f (σ )-location and g(σ )-location problems.
|