# On the Location of a Constrainedk-Tree Facility in a Tree Network with Unreliable Edges

Authors: Abdallah W. Aboutahoun; Eman Fares
Journal: Journal of Applied Mathematics
 (2019)

---

## Abstract

Given a tree networkT with n vertices where each edge has an independent operational probability, we are interested in finding the optimal location of a reliable service provider facility in a shape of subtree with exactly k leaves and with a diameter of at most l which maximizes the expected number of nodes that are reachable from the selected subtree by operational paths. Demand requests for service originate at perfectly reliable nodes. So, the major concern of this paper is to find a location of a reliable tree-shaped facility on the network in order to provide a maximum access to network services by ensuring the highest level of network connectivity between the demand nodes and the facility. An efficient algorithm for finding a reliable (k,l) – tree core of T is developed. The time complexity of the proposed algorithm is Olkn. Examples are provided to illustrate the performance of the proposed algorithm.


---

## Body

## 1. Introduction

The classical location theory is concerned with the location of a service facility on a network. This facility can be a single point or a specified number of points, located at either a vertex or along an edge of the network. The location of the facility depends on the distances between the demand vertices (customers) and their respective server. The location of special types of subgraphs such as paths, trees, or forests is considered as an extensive facility location problem. These facilities formed of connected structures have many applications in the fields such as transportation, communication, and computer sciences. The three criteria for optimality which are extensively studied in the literature are the following:(1)
The median criterion or the minisum criterion in which the sum of the distances from all the vertices of the network to the facility is minimized.(2)
The center criterion or the minimax criterion in which the maximum distance from the demand vertex to the facility is minimized.(3)
The centdian criterion in which the convex combination of the weighted average distance and the maximum weighted distance from the facility to the demand points is minimized.In recent years, there has been a growing interest in studying the location of facilities formed of connected structures which are also called extensive facilities on a tree network. The location of a path-shaped and tree-shaped facilities under the above three criteria has been studied by a number of authors. In this paper, we are studying the location of a reliable tree-shaped facility on a tree network with unreliable edges. A core of a tree is defined to be a path that is optimal with respect to the property of minimizing the sum of the distances from each vertex in the tree to the path (criterion 1). The generalization of the core of the tree is ak-tree core which is a subtree containing exactly k leaves that minimizes the sum of the distances from each vertex in the tree network to the selected k-tree core facility. The k,l-tree core is a subtree with diameter at most l having k leaves which minimizes the sum of the distances or the weighted distances from all vertices in the tree network to this subtree facility.Finding the core of a tree network has been considered by a several authors. Becker et al. [1] presented two efficient algorithms for finding the l-core of a tree. For unweighted trees they developed an On2 time algorithm, while for weighted trees they provided a procedure with time complexity of Onlog2n. Peng and Lo [2] presented a recursive Onlog⁡n time algorithm for finding a core of specified length, that is, a path with length equal to a specified value l, in unweighted trees. Morgan and Slater [3] presented a linear time algorithm for finding the core of a tree network. Minieka and Patel [4] explored some properties of a core of a specified length of a tree network. A 2-core of a tree T is a set of 2 mutually disjoint paths in T that minimizes the sum of the distances of all vertices in T from any of the two paths. Wang [5] developed an On time algorithm for the 2-core problem, where n is the number of vertices in T. Becker et al. [6] considered the problem of finding an optimal location of a path-shaped facility on a tree network using combinations of the center and the median criteria. They studied two problems: 1 finding a path which minimizes the sum of the distances such that the maximum distance from the vertices of the tree to the path is bounded by a fixed constant and such that the length of the path is not greater than a fixed value; 2 finding a path which minimizes the maximum distance with the sum of the distances being not greater than a fixed value and with bounded length. They gave Onlog2n divide-and-conquer algorithms.Wang et al. [7] developed two algorithms for finding a (k,l)-tree core of a tree T. The first algorithm has O(n2) time complexity for the weighted tree (each edge has an arbitrary length). The second algorithm has O(lkn) time complexity for the unweighted tree (the lengths of all edges are 1). Also, Peng et al. [8] presented two algorithms to find a k-tree core of a tree with n vertices. The time complexities of these two algorithms are Okn and Onlog⁡n. Becker et al. [9] provided two algorithms; the first one for unweighted trees has time complexity of On2, whereas the second one for weighted trees has time complexity of On2log⁡n. Shioura and Uno [10] proposed a linear time algorithm for finding a k-tree core of a tree network. Minieka [11] described methods for finding an optimal location for a path-shaped or tree-shaped facility of a specified size in a tree network. Four optimization criteria were examined: minimizing distancesum, minimizing eccentricity, maximizing distancesum, and maximizing eccentricity. Solution algorithms were presented. Kim et al. [12] studied the problem of locating a subtree facility on a tree network. They considered the cost of establishing the subtree facility in addition to the transportation cost associated with the travel of customers to the subtree facility. The objective function is to select a tree-shaped facility that will minimize the sum of the setup cost and the total transportation cost. Tamir er al. [13] developed an algorithm of Onlog⁡n time complexity for finding the optimal location of a tree-shaped facility of a specified size in a tree network with n nodes, using the centdian criterion: a convex combination of the weighted average distance and the maximum weighted distance from the facility to the demand points (nodes of the tree). Tamir et al. [14] studied the location of a subtree facility on a tree network, both discrete and continuous under the condition that existing facilities are already located. They used the center and the median criteria.The problems of finding a single point, a path, or a subtree on tree network with distance edges have been studied extensively in literature, a single facility location problem on a network with unreliable edges has been also considered by a number of authors. Melachrinoudis and Helander [15] addressed the reliable 1-median (relisum) location problem of a single facility on an undirected tree with unreliable edges. The objective of the problem is to maximize the expected number of nodes reachable by operational paths. They developed two polynomial algorithms; an O(n3) algorithm which is a modification of the Floyd-Warshall algorithm for finding all pairs of the shortest paths in a graph and an O(n2) algorithm which set up a depth-first node traversal and the decomposition nature of an operational path. Xue [16] presented a linear time algorithm for the same problem which was displayed by Melachrinoudis and Helander [15]. Helander and Melachrinoudis [17] introduced path reliability measures for the expected number of accidents over a given planning horizon. Reliability refers to the probability of a hazmat transport vehicle completing a journey from an origin to a destination. They presented two different locations of the modeling frameworks: the reliable 1-median and a general framework for considering multiple routes. Santiváñez et al. [18] considered the problem of location a single facility on an undirected network with unreliable edges under the center criterion. The objective function is formally stated as either minimizing the maximum expected number of unsuccessful responses to demand requests over all nodes, called the reli-minmax problem, or maximizing the minimum expected number of successful responses to demand requests over all nodes, called the reli-maxmin problem. The problem is termed the reliable 1-center problem and finds applications in telecommunication and computer networks. As for subproblems of the most general reliable 1-center problem, Eiselt et al. [19] presented the problem of locating p facilities on a network so that the total expected demand disconnected from the facilities is minimized. It is supposed that every edge has a probability of failure and that failures can never occur on two edges simultaneously. Eiselt et al. [20] showed how to optimally locate p facilities on a network with unreliable node or edge in order to minimize the expected demand disconnected from the facilities. Ding and Xue [21] studied the problem of locating a node which maximizes the expected number of nodes that are reachable from it. Such a node is called a most reliable source (MRS) of the network. They presented a linear time algorithm for computing a most reliable source on an unreliable tree network where all links are immune to failures and each node has an independent transmitting probability and an independent receiving probability. Puerto et al. [22] considered the problem of locating two path-shaped facilities minimizing the expected service cost in the long run, assuming that paths may become unavailable and their failure probabilities are known in advance. They provided a polynomial time algorithm that solves the 2 unreliable path location problem on tree networks in On2 time, where n is the number of vertices. Ding et al. [23] studied the problem of finding the 2-most reliable source (2-MRS) in an unreliable tree network. The 2-MRS problem aims to find a node pair from which the expected number of reachable nodes or the minimum reachability is maximized (i.e., Sum-Max 2-MRS and Min-Max 2-MRS).The reliable(k,l)-tree core problem is stated as finding the optimal location of a tree-shaped facility (service provider) in an unreliable tree network with a diameter of at most l and having k leaves which maximizes the expected number of nodes that are reachable from it. This problem considers only edge failures while the nodes and the service provider facility are considered perfectly reliable. So, the model we present in this paper is stochastic in the sense that edges fail randomly which may cause a disconnection between demand nodes and service provider facility. The major concern of this work is to find a location of a service provider facility in order to provide a maximum access to network services, but in the context of connectivity, i.e., the probability that an operational path exists between two points of the network, and therefore the connectivity of the network is measured using path reliability.For any two verticesv,u∈V, the vertex v is called reachable from u (or u is called reachable from v) if there exists an operational path between them, i.e., every edge in this path is in an operational state. The objective is to identify a subtree S that has exactly k leaves, diameter of at most l and the cumulative reliability from V to S, ∑v∈VRv,S is maximized. This subtree S is the reliable k,l-tree core facility of T. The reliable k,l-tree core problem is motivated from a distributed database application in computer science; see Wang et al. [7] and Peng et al. [8].The remainder of this paper is organized into five sections. In Section2, we present notation, definitions, and some preliminary results. Section 3 is devoted to the formulation and a full description for the proposed problem. In Section 4, we present an efficient algorithm for finding a reliable (k,l)-tree core of T. In Section 5, a numerical example is provided to illustrate the efficiency of the proposed algorithm. Finally, in Section 6, we give a concluding remarks and future research.


## 2. Definitions and Preliminaries

LetT=V,E be a tree network, where V=1,2,3,…,n is the node set and E=e=i,j:i,j∈V is the edge set. Let Pv,u be a unique path in treeT from node v to node u and let dv,u be its length which is defined in this study to be the number of edges in the path. Let VPv,u and EPv,u denote the set of nodes and edges on the path Pv,u, respectively. Let pi,j denote the probability that edge i,j∈E in operational state such that 0<pi,j≤1 and qi,j=1-pi,j is the probability that the edge i,j∈E is in a failed state. All vertices are assumed to be perfectly reliable and any vertex is called a leaf vertex if the number of edges incident to it is equal to 1. The number of edges that can be in a failed state has no limitations, we assume that failures occur independently. Let Tr be the tree obtained by making T rooted at a vertex r∈V. The diameter of Tr is maxv,u∈V⁡d(v,u) while the height of Tr is maxu∈V⁡d(r,u), where r is called the root of tree T. Let v be an a vertex in Tr, and we denote by Tvr a subtree of Tr rooted at a vertex v∈V. Let Nv denote the set of children of v and fv denote the parent of v. If the vertex v is adjacent to r, Tvr is called a subtree of r.For each edgee=i,j we call taile=i the endpoint of e closest to the root r, and we call heade=j the endpoint of e farthest to the root. Each edge e divides Tr into two disjoint subtrees denoted by Theader and Ttailer. The subtree Theader=Tjr is a subtree of Tr rooted at a vertex j as defined above and the subtree Ttailer=Tr\Theader is a subtree of Tr rooted also at r but induced by the set of vertices V\VTheader, where VTheader is the set of vertices of the subtree Theader. If v and u are two vertices in an unreliable communication network, we use Rv,u to denote the reliability that a message can be transmitted correctly from v to u. Let S be a subtree of T and VS be the set of nodes of S. The expected number of nodes reachable by operational paths from the nodes of subtree S of T is called the reachability or connectivity of the subtree S.A reliable(k, l) −tree core is a subtree S with k leaves and with a diameter of at most l which maximizes the expected number of nodes that are reachable by operational paths from the nodes of S. In other words, we seek for a subtree S of T with diameter of at most l, having k leaves, which maximizes the expected number of successful responses to demand requests over all nodes. A demand request is originating at a node v which requires that some entity moves from the service provider located at a subtree S to node v along some path in the tree network.Definition 1.
Under the assumption that edges fail independently, the reliability of a pathPv,u is defined as the product of the reliability of arcs in the path EPv,u, i.e.,(1)RPv,u=Rv,u=∏i,j∈EPv,upi,jand the probability that at least one edge in the path Pv,u has failed deeming the path unusable is(2)1-Rv,u=1-∏i,j∈EPv,upi,jNote thatRPv,u=pv,u when Pv,u consists of one edge v,u∈E and RPv,v=1 when v=u. Also, note that pv,u=pu,v and Rv,u=Ru,v as long as all vertices have the same weight. The path Pv,u is operational if and only if all edges of Pv,u are operational simultaneously. Since for any v,u∈V there exists a unique path Pv,u in Tr connecting v and u, then it always holds that RPv,u=Rv,u in Tr.Definition 2.
For a rooted treeTr, the total connectivity of any vertex v∈V or the expected number of nodes reachable from v∈V is defined by(3)RSv=∑u∈VRv,u=1+∑u∈V\vRv,uwhere pv,v=1.For a vertexv∈V and a path P of T, the reliability from v to P is(4)Rv,P=maxu∈VPRu,vAlso, for a vertexv∈V and a subtree S of T, the reliability from v to S is(5)Rv,S=maxu∈VSRu,vDefinition 3.
For a rooted treeTr, the total connectivity of any path P is the sum of the reliabilities from all the vertices of T not in P to the path P(6)RSP=∑v∉PRv,Pwhere Rv,P is the maximum reliability from v∈V\VP to a vertex in P.Definition 4.
For a rooted treeTr, the total connectivity of any subtree S is the sum of the reliabilities from all the vertices of T not in S to the subtree S(7)RSS=∑v∉SRv,Swhere Rv,S is the maximum reliability from v∈V\VS to a vertex in S.Following the same notation developed by Ding and Xue [21], let Tr be a rooted tree at any vertex. For any vertex v in Tr, let Tαv be the subtree of Tr rooted at vertex v. Let Vαv be the set of vertices of Tαv and let Tβv be the subtree induced by the set of vertices Vβv=V-Vαv such that Vαv∪Vβv=V and Vαv∩Vβv=ϕ. If v is a leaf, then Vαv=v and Vβv=V-v. If v=r, then Vβv=ϕ and Vαv=V. The quantities corresponding to Tαv are often referred as below quantities, while the ones corresponding to Tβv are referred as upper quantities. The two subtrees Tαv and Tβv are connected by the edge fv,v, see Figure 1.Figure 1
The decomposition of the rooted treeTr at node v into two subtrees Tαv and Tβv.Based on the previous decomposition ofTr at node v, Theorem 5 presents two formulas for computing the connectivity of a node v in the subtrees Tαv and Tβv. We will use RSαv to denote the expected number of nodes in Vα(v) which can be reached from node v and use RSβv to denote the expected number of nodes inVβ(v) which can be reached from node v.Theorem 5 (see [21, 23]).
For any nodev∈V, the reliability sums RSα(v) and RSβv are given by(8)RSαv=1+∑w∈NvRSαwpv,w(9)RSβv=RSβfv+1+∑z∈Nfvz≠vRSαzpz,fvpfv,vwhere N(v) denotes the set of nodes which consists of all children of v. If v is a leaf then RSα(v)=1 and if v is a root of tree Tr then RSβ(v)=0.Proof.
See Ding and Xue [21].Based on the formulas in Theorem5 for computing the expected number of nodes in the two subtrees Tαr and Tβr that can be reached from v, the next lemma gives the combination of RSαv and RSβv to find expected number of nodes in Tr=Tαr∪Tβr∪fv,v that can be reached from v which is also called the total connectivity of v.Lemma 6.
For a rooted treeTr, the total connectivity of any vertex v∈V or the expected number of nodes reachable from v∈V is given by(10)RSv=RSαv+RSβvProof.
S e e Ding and Xue [21].Theorem5 and Lemma 6 give the connectivity or the reachability of a node in an unreliable tree network. The next six lemmas give formulas for computing the cumulative reliability of an extensive facility in the form of single edge path-shaped facility, path-shaped facility, and a tree-shaped facility. These formulas generalize the results of Theorem 5 and Lemma 6 to present the connectivity of a path or a subtree instead of a node, also, using the concept of reliability saving which is very useful for computing the cumulative reliability from T to a given path or subtree facility.Lemma 7.
For each edgee=(u,v), where u=tail(e) and v=head(e), the expected number of nodes reachable by operational paths from the service facility located as a single edge path-shaped facility which is called the relisum of this edge e is given by(11)RSe=u,v=1-pu,vRSαv+RSuProof.
(12) R S e = u , v = R S h e a d e v + R S t a i l e u = R S α v + R S u - p u , v R S α v = 1 - p u , v R S α v + R S uwhere,(13)RSheadev=RSαvand(14)Rtaileu=RSu-pu,vRSαvThe relisum of the path-shaped facility with only one edgeRSe can be evaluated also by (15)RSe=u,v=RSu:pu,v=1=RSv:pu,v=1=2+∑vk∈NvRSαvkpv,vk+∑wt∈Nuwt≠vRSαwtpu,wt+RSβuWe now introduce the definition of the reliability saving of a path which is the most important measure for guiding the optimal selection of a path with maximum connectivity or reachability starting from any vertex of the tree.Definition 8.
Given a pathPv,u and a path Pu,w with edges disjoint from Pv,u, the reliability saving of Pu,w with respect to Pv,u is the increment of the reliable sum obtained by adding Pu,w to Pv,u, that is,(16)δPv,u,Pu,w=RSPv,w-RSPv,uIf the first path consists of only one vertexv, we simply write δv,Pv,w=RSPv,w-RSv. The reliability saving of a path Pv,u in the subtree Tαv is defined by δαv,Pv,u=RSαPv,u-RSαv.The reliability saving of a given pathPv,u in the subtree Tαv is defined recursively as follows:(17)δαv,Pv,u=δαfu,e=v,u=1-pv,uRSαu,v=fuδαv,Pv,fu+δαe=fu,u,v≠fuwhereδαfu,e=fu,u gives the reliability saving of a single edge path facility Pv,u=v,u in the subtree Tαv.The following lemma gives two important formulas for calculating the reliability sum and the reliability saving of a given path in the subtreeTαv.Lemma 9.
LetP(v, u) be a path in Tαv in the form v=v1,v2,…,vh=u, then we have(18)RSαPv,u=∑i=1h-1RSαvi-RSαvi+1pvi,vi+1+RSαvhand(19)δαv,Pv,u=∑i=1h-11-pvi,vi+1RSαvi+1Proof.
The reliability sumRSαPv,u of a given path Pv,u in the subtree Tαv is the sum of the reliability sums RSαvi of the vertices in the path Pv,u excluding the edges of this path. (20)RSαPv,u=1+∑vk1∈Nv1\v2RSαvk1pv1,vk1+1+∑vk2∈Nv2\v3RSαvk2pv2,vk2+⋯+1+∑vkh-1∈Nvh-1\vhRSαvkh-1pvh-1,vkh-1+1+∑vkh∈NvhRSαvkhpvh,vkh which can be written in the form (21)RSαPv,u=1+∑vk1∈Nv1RSαvk1pv1,vk1-RSαv2pv1,v2+1+∑vk2∈Nv2RSαvk2pv2,vk2-RSαv3pv2,v3+⋯+1+∑vkh-1∈Nvh-1RSαvkh-1pvh-1,vkh-1-RSαvhpvh-1,vh+1+∑vkh∈NvhRSαvkhpvh,vkhHence,(22)RSαPv,u=RSαv1-RSαv2pv1,v2+RSαv2-RSαv3pv2,v3+⋯+RSαvh-1-RSαvhpvh-1,vh+RSαvh=∑i=1h-1RSαvi-RSαvi+1pvi,vi+1+RSαvhThis proves formula (18)
Sinceδαv,Pv,u=RSαPv,u-RSαv and by using formula (18), we get(23)δαv,Pv,u=∑i=1h-11-pvi,vi+1RSαvi+1The following lemma shows the using of the reliability saving concept in computing the reliability sum fromTr to a given path.Lemma 10.
For allu∈V\v, the reliability sum of the path Pv,u is(24)RSαPv,u=RSαv+δαv,Pv,uProof.
The proof follows immediately from the previous lemma.The reliability saving can be calculated recursively by using a bottom up procedure as stated by the following lemma.Lemma 11.
LetPv,u be a path in a tree Tαv. The reliability saving of the path Pv,u can be defined recursively by(25)δαv,Pv,u=δαv,Pv,fu+δαfu,e=fu,u
whereδαfu,e=fu,u=1-pfu,uRSαu.Proof.
(26) δ α v , P v , u - δ α v , P v , f u = R S α P v , u - R S α v - R S α P v , f u - R S α v = R S α P v , u - R S α P v , f u = 1 - p f u , u R S α uFor a subtreeS and a vertex v∉S, let TSv be the subtree in T induced by the vertex set VSv=w:Pw,v∩S=ϕanddw,S≥dv,S. If we regard T as a tree rooted at S, TSv can be seen as a subtree rooted at v. If the subtree S becomes larger, the reliability sum RSS increases strictly. The following lemma shows that the reliability sum of the subtree S increases by adding a path to it.Lemma 12.
LetPv,u be any path in a tree Tαv and let S be any subtree of Tr which intersects with the path Pv,u at node v then the relisum of the new subtree S∗=S∪Pv,u is(27)RSS∗=RSS∪Pv,u=RSS+δαv,Pv,uProof.
(28) R S S ∪ P v , u - R S S = ∑ w ∈ V R w , S ∪ P v , u - R w , S = ∑ w ∈ T S v R w , P v , u - R w , v + ∑ w ∉ T S v R w , S - R w , S = ∑ w ∈ T S v R w , P v , u - R w , v + ∑ w ∉ T S v R w , v - R w , v = ∑ w ∈ V R w , P v , u - R w , v = R S P v , u - R S v = δ α v , P v , uWe consider increasingRSS by adding a path P to a subtree S. The following equation holds for the increase of the reliability by addition of a path to a subtree.Lemma 13.
LetP(v,u) be a path from vertex v to vertex u in a tree Tαv and S is any subtree of Tr such that
P v , u ∩ S = v, then(29)RSS∪Pv,u-RSS=RSαPv,u-RSαvProof.
The proof is straight forward by using Lemma12 and Lemma 10.Definition 14.
In [9], given a path P having an even (odd) length l, the midpoint of P is a vertex (edge) whose removal divides P into two paths with length l/2l-1/2.


## 3. The Reliablek,l-Tree Core Problem

For any subtreeS of T with exactly k leaves and with diameter ≤l, let c be the unique center of S and suppose that c is a vertex. Let h=l/2 be the height of the subtree S in T and orient the tree T into Tc, then S is a subtree rooted at c with height ≤h and having k leaves.Letc be the midpoint of a path Pv,u between any two vertices v and u of length ≤l. The center of unweighted tree T occurs at the midpoint of the longest path in the tree, this result is presented by Handler [24]. The center of a tree is either of one vertex or an edge and it is unique. The following two sets Γ1 and Γ2 define the centers of a subtrees with diameters ≤l.(30)Γ1=c:cisthecentervertexofthepathwithevenlengthPv,u,wherev,u∈Vanddv,u≤l(31)Γ2=e:eisthecenteredgeofthepathwithoddlengthPv,u,wherev,u∈Vanddv,u≤lTherefore, there exists a point inΓ1 or an edge in Γ2 that is the center of a k,l-tree core of T. All the subtrees of the tree T with diameter ≤l will be classified by the midpoints of their diameters. Then, we search for a k leaves subtree in the class of the subtrees of T having a given c as a midpoint. In other words, each c∈Γ1 or c∈Γ2 is the center of a set of subtrees of T with diameter ≤l, and the reliable k,l-tree core is one of these subtrees having k leaves and maximum reliability sum.For each pathPv,u with length less than or equal l and midpoint c∈Γ1, the tree T is going to be oriented into a rooted tree at c and denote it by Tc. If c∈Γ2 which is an edge, then we contract it into a vertex and we continue to call the resulting vertex c and the resulting rooted tree Tc.Define(32)Can_Set_Lvsc=u:u∈V,du,c≤handdw,c>hforeverychildofwofuto be the candidate set of leaves for the subtree rooted atc, where h=l/2 if c is the center of an even length path and h=l-1/2 if c is the center edge of an odd length path. Note that it is not necessary that the vertices of Can_Set_Lvsc are leaves in Tc, and it is the set of vertices at a distance h or less from the root c of the tree such that their children vertices are more than h distance away from c. For example, consider the rooted tree Tc in Figure 3. If h=3, we have Can_Set_Lvsc=v4,v6,v7,v9,v10,v12,v13,v14,v15,v16,v17,v18,v19. All leaves of the rooted reliable k,h-tree core of Tc are vertices in Can_Set_Lvsc. Every vertex v∈Can_Set_Lvsc is called a candidate with respect to h. The selected k candidates from Can_Set_Lvsc can not be contained in the same subtree of c. Otherwise, c is not contained in the induced subtree by these vertices.The stochastic optimization problem considered in this paper is the following: Given a tree network with unreliable edges and given two parametersk and l, the problem is to identify a subtree S⊆T with exactly k leaves, diameter ≤l and the reliability sum ∑v∈VRv,S is maximized. If l exceeds the diameter of T, then the reliable k,l-tree core problem is just the k-tree core problem.Problem 15.
Given a rooted treeTc, find a reliable k,l-tree core rooted at c of Tc with maximum reliability sum.LetTvc be a subtree rooted at a vertex v in the tree Tc. If v∈V is a vertex with dc,v≤h, the candidate u∈Can_Set_Lvsc∩VTvc dominates v if δv,Pv,u>δv,Pv,z for all z∈Can_Set_Lvsc∩VTvc or δv,Pv,u=δv,Pv,z and u>z. This means that the path Pv,u has a maximum reliability saving among all paths from v to vertices in Can_Set_Lvsc∩VTvc. If the vertex u dominates the vertex v, then every vertex on the path Pv,u is also dominated by u. In constructing the reliable subtree k,h- tree core we define Δu to be the farthest ancestor vertex of u that is dominated by it. Given u∈Can_Set_Lvsc, the reliability saving of paths in Tc is defined by(33)Ωu=δc,Pc,uifΔu=cδfΔu,PfΔu,uotherwiseSorting the vertices in Can_Set_Lvsc according to their reliability saving Ωu, u∈Can_Set_Lvsc. The rank of a vertex u∈Can_Set_Lvsc is denoted by ranku and it is the number of vertices z∈Can_Set_Lvsc such that either Ωz>Ωu or Ωz=Ωu and z≥u. We denote the vertex with rank i in Can_Set_Lvsc by ai, 1≤i≤Can_Set_Lvsc.The following Lemma states a formula for calculating the reliability sum from the vertices ofTc to the subtree induced by the set of vertices c,a1,a2,…,ai.Lemma 16.
(34) R S c , a 1 , a 2 , … , a i = R S c + ∑ j = 1 i Ω u j ,  for  all i = 1,2 , … , C a n _ S e t _ L v s cProof.
LetSi=c,a1,a2,…,ai,i=1,2,…,Can_Set_Lvsc. By definition, a1 dominates the root cΔa1=c. Thus, Ωa1=δαc,Pc,a1 and S1 is the path connecting the root c with the vertex a1, RSS1=RSc+δαc,Pc,a1=RSc+Ωa1. For any i>1,Si differs from Si-1 only in one path PfΔai,ai. By Lemma 12, RSSi=RSSi-1+δαfΔai,PfΔai,ai=RSSi-1+Ωai for 1<i≤Can_Set_Lvsc. Recursively, it is easy to note that RSSi=RSc+∑j=1iΩuj,i=1,2,…,Can_Set_Lvsc.If the nonincreasing set of verticesΛc=a1,a2,…,ak is contained in VTjc∩Can_Set_Lvsc,j∈Nc, then the subtree induced by Λc will be a subtree of c rooted at vertex j and does not include the root c. So, let us define(35)MAX_δc,Pc,u=maxz∈Can_Set_Lvscδc,Pc,z=δc,Pc,a1SEC_MAX_δc,Pc,w=maxz∈Can_Set_Lvsc,Pc,a1∩Pc,z=cδc,Pc,z=δc,Pc,atM A X _ δ c , P c , u represents the maximum reliability saving of a path connecting the root c to a vertex in Can_Set_Lvsc which is denoted by a1. SEC_MAX_δc,Pc,w represents the second maximum reliability saving of a path connecting the root c to a vertex in Can_Set_Lvsc which is denoted by at, where Pc,a1∩Pc,at=c. If at∈Λc, then the induced subtree Λc represents the required reliable k,h- tree core of Tc. If at∉Λc, then Λc is included in one subtree Tjc, j∈Nc so Λc is the subtree rooted at j and the root c is not included in the required subtree. To avoid this situation, ak in Λc will be replaced by at, where t is the smallest integer such that(36)Λc=a1,a2,…,ak-1,akIft≤ka1,a2,…,ak-1,atotherwiseNote thatΛc maximizes ∑u∈SΩu over all subsets S⊆Can_Set_Lvsc such that S=k and the k candidates in S are not all contained in the same subtree of c. The following lemma gives the reliability sum of the optimal subtree Λc among all induced subtrees of subsets S⊆Can_Set_Lvsc.Lemma 17.
(37) R S Λ c = R S c + ∑ u ∈ Λ c Ω uProof.
c , a 1 , a 2 , … , a k = a 1 , a 2 , … , a k if t≤k, which means the subtree induced by the subset of vertices a1,a2,…,ak⊆Can_Set_Lvsc contains the first and the second reliability saving paths passing through the root c, thus the lemma holds by using the previous lemma. Let t>k, then Λc=c,a1,a2,…,ak-1,at differs from c,a1,a2,…,ak-1 in only the path Pc,at. Then, (38)RSΛc=RSc,a1,a2,…,ak-1+δαc,Pc,at=RSc+∑j=1k-1Ωaj+Ωat=RSc+∑u∈ΛcΩu where a1,a2,…,ak-1⊆VTjc∩Can_Set_Lvsc, j∈Nc and the path Pc,at has the highest reliability saving rank among all vertices that are not contained in Tjc, fΔat=c. Hence, δαc,Pc,at=Ωat.Also,RSΛc can be calculated by a different formula which is stated in the next lemma.Lemma 18.
The reliability sum of the subtreeS=Λc can be computed using the following formula:(39)RSS=RSPc,a1+∑u∈Λc\a1ΩuThe terms of candidates and values can be generalized to the case that both the root of the tree and the height of the subtrees to be considered are not fixed. The root of the tree can be any vertexi in T and the subtrees considered are those of height m≤h. For a given pair of i and m, we define(40)Can_Set_Lvsi,m=v:v∈VTi,di,v≤m,anddi,u>mforeverychilduofvThe value of the candidateu∈Can_Set_Lvsi,m is denoted by Ωi,m,u which is defined similarly as Ωu, the maximum reliability saving of a path from a vertex u∈Can_Set_Lvsi,m to a vertex w∈VTic such that Δu=w.For eachj∈Ni, we define the candidate set(41)Can_Set_Lvsi,m,j=Can_Set_Lvsi,m∩VTji=Can_Set_Lvsj,m-1The following lemma shows that the reliability saving valueΩi,m,u of any path can be computed recursively by bottom up procedure.Lemma 19.
Leti be a vertex in Tc and j∈N(i). We have(a)(42)Can_Set_Lvsi,m,j=⋃v∈NjCan_Set_Lvsj,m-1,v(b)(43)Ωi,m,u=Ωj,m-1,u+1-pi,jRSαjifudominatesjΩj,m-1,uotherwiseProof.
From (41), the candidate set of leaves Can_Set_Lvsi,m,j consists of the set of vertices u∈VTji such that di,u≤m and di,w>m for every child w of u as shown in Figure 2. Since the length of the edge i,j is 1, a vertex v∈VTji and v∈Can_Set_Lvsi,m if and only if v∈Can_Set_Lvsj,m-1. This shows that Can_Set_Lvsi,m,j consists of the union of Can_Set_Lvsj,m-1,v over all v∈Nj. Part b follows immediately from definition (33) of Ωu and Lemma 9.Figure 2
The candidate set of leavesCan_Set_Lvsi,m,j in the subtree Tji.Figure 3
A rooted tree networkTc with 29 vertices and 28 edges.For any rooted subtreeTic of Tc, the set of paths with maximum reliability saving from vertices in Can_Set_Lvsi,m,j to the vertices of Tji can be constructed by using the definition of Ωi,m,u in part b of the previous lemma.The vertices inCan_Set_Lvsi,m must be sorted in a descending order according to their reliability saving values Ωi,m,u and for any subset S⊆Can_Set_Lvsi,m, ranku,S denotes the rank of the vertex u∈S. A reliable k,h-tree core of a rooted tree Tc must contain as a subtree a reliable k-1,h-tree core.


## 4. Algorithm

In this section, an algorithm for finding the location of a reliablek,l-tree core facility in a tree network with unreliable edges is presented. The algorithm first uses the dynamic programming technique to compute a table Φ in bottom–up fashion. Then, it uses the table to compute Λc for each c∈Γ1∪Γ2 efficiently. Finally, it finds a reliable (k,l)-tree core of T by determining the induced subtree Λc of the top ranked k vertices of Can_Set_Lvsc that maximizes RSΛc. Given a tree network T with unreliable edges, the proposed algorithm identifies a subtree S which satisfies the following:(1)
Orient the input treeT into a rooted tree Tc for every c∈Γ1∪Γ2.(2)
c is the root of S and has degree at least 2.(3)
S has exactly k leaves.(4)
S has height at most h.(5)
The reliability sum of the subtreeS,RSS is maximized.Remark 20.
Each reliablek,l-tree core Λc must contain the two paths Pc,a1 and Pc,at with the maximum and the second maximum reliability saving such that Pc,a1∩Pc,at=c.The algorithm uses dynamic programming technique to compute a table entryΦi,m,j which stores a set of up to k candidates and their values Ωi,m,j.For the subtreeTuv and u∈Nv, a recursive formula of Φv,m,u is given as follows:(44)Φv,1,u=u,δv,Pv,u=v,1-pv,uRSαuifm=1and(45)Φv,m,u=u,1-pv,uifm>1anduisaleafWhenm>1 and u is not a leaf, Φv,m,u can be recursively computed as follows:(46)Φv,m,u=α∗,β∗+1-pv,uRSαu∪α,β:α,β∈Z,2≤rankα,Z≤kwhere(47)Z=⋃w∈Nu,w≠vΦu,m-1,w,andα∗,β∗∈Zwithrankα∗,Z=1Z contains the set of leaves α∈Can_Set_Lvsv,m,u in the subtree Tuv of v with their values β; among them the best k leaves can be chosen according to their values of reliability saving.For example, consider the rooted treeTc depicted in Figure 3. Let h=3, we show how Φc,3,v1 can be computed. At the beginning the set of candidate leaves is Can_Set_Lvsc,3,v1=v4,v6,v12,v13,v14. The computation of Φv1,2,v5 requires the computation of Z=⋃w∈Nv5,w≠v5Φv5,1,w=v12,0.086,v13∗,1.88902,v14,0.285. Hence, (48)
Φ
v
1
,
2
,
v
5
=
v
13
,
1.88902
+
1
-
p
v
1
,
v
5
R
S
α
v
5
∪
v
12
,
0.086
,
v
14
,
0.285
=
v
13
,
1.88902
+
1
-
0.482
3.62398
∪
v
12
,
0.086
,
v
14
,
0.285
=
v
13
,
3.76624
,
v
12
,
0.086
,
v
14
,
0.285Note thatRSαv5 in Φv1,2,v5 can be calculated as follows:(49)RSαv5=1+∑w∈NvRSαwpv,w=1+RSαv120.914+RSαv130.345+RSαv140.715=1+10.914+1+RSαv200.502+RSαv210.647+RSαv220.7350.345+10.715=1+0.914+1+0.502+0.647+0.7350.345+0.715=3.62398Recursively, to computeΦc,3,v1, we need the computation of Z, (50)Z=⋃w∈Nv1,w≠v1Φv1,2,w=Φv1,2,v4∪Φv1,2,v5∪Φv1,2,v6=v4,0.476,v13∗,3.76624,v12,0.086,v14,0.285,v6,0.131Hence,(51)Φc,3,v1=v13,3.76624+1-pc,v1RSαv1∪v4,0.476,v12,0.086,v14,0.285,v6,0.131=v13,4.403763,v4,0.476,v12,0.086,v14,0.285,v6,0.131So, the computation of the table entriesΦc,3,v1,Φc,3,v2 and Φc,3,v3 is summarized in Table 1. If k=4 and h=3, a reliable 4,3-tree core for the considered rooted tree Tc depicted in Figure 3 is shown in Figure 4 with double lines edges. In this case, Λc=v13,v15,v16,v18, then the induced subtree Λc is the optimal reliable 4,3-tree core in Tc.Table 1
Calculating the table entriesΦ[c,3,v1], Φ[c,3,v2], and Φ[c,3,v3].
v,u Φ v 5 , 1 , v Φ v 1 , 2 , v Φ c , 3 , v 1 v5,v12 v 12 , 0.086  v5,v13 v 13 ∗ , 1.88902  v5,v14 v 14 , 0.285  v1,v4  v 4 , 0.476  v1,v5  v 12 , 0.086 v 13 ∗ , 3.76624 v 14 , 0.285  v1,v6  v 6 , 0.131  c,v1   v4,0.476v6,0.131v12,0.086v13,4.403763v14,0.285  v,u Φ v 8 , 1 , v Φ v 2 , 2 , v Φ c , 3 , v 2  v8,v15 v 15 ∗ , 0.96163  v8,v16 v 16 , 0.67494  v2,v7  v 7 , 0.538  v2,v8  v 16 , 0.67494 v 15 ∗ , 3.0041  c,v2   v7,0.538v16,0.67494v15∗,3.1839  v,u Φ v 11 , 1 , v Φ v 3 , 2 , v Φ c , 3 , v 3  v11,v17 v 17 , 0.366  v11,v18 v 18 ∗ , 1.5312  v11,v19 v 19 , 0.418  v3,v9  v 9 , 0.487  v3,v11  v 17 , 0.366 v 18 ∗ , 1.9358 v 19 , 0.418  v3,v10  v 10 , 0.379  c,v3   v9,0.487v10,0.379v17,0.366v18∗,3.1944v19,0.418Figure 4
The inducedΛc optimal reliable 4,3-tree core of Tc shown in double lines.If the four leaves inCan_Set_Lvsc,3 with the highest values are contained in one subtree of c, for example Tv1c. The fourth ranked entry α4,β4 in Φc,3,v1 will be replaced with the highest ranked entry in Φc,3,v2∪Φc,3,v3 to construct Λc such that the subtree induced by Λc will contain c. Figure 5 is a rooted tree at the vertex v2∈Γ1, so by the same procedure the optimal reliable tree core Λv2can be computed (see Algorithm 1).Algorithm 1
Inputs: A tree T with an operational probability associated with each edge and two positive integers k,l. Outputs: A reliable k,l-tree core S∗ with diameter of at most l and having exactly k leaves which maximizes the reliability sumRSS∗. Initialization: R S ∗ = 0 and S∗=ϕ begin For each c∈Γ1∪Γ2do Orient the input tree T into a rooted tree Tc. For each u,v∈Edo If v is a leaf then Φ u , 1 , v ≕ v , 1 - p u , v Else Φ u , 1 , v ≕ v , 1 - p u , v R S α T v u End If End For For m ≕ 2 : h do For each j∈Ncdo If j is a leaf then Φ c , m , j ≕ c , 1 - p i , j Else Φ c , m , j = α ∗ , β ∗ + 1 - p i , j R S T j i ∪ α , β : α , β ∈ Z , 2 ≤ r a n k α , Z ≤ k where Z = ⋃ v ∈ N j Φ j , m - 1 , v   a n d   α ∗ , β ∗ ∈ Z , r a n k α ∗ , Z = 1 End If End For End For Sort in a decreasing order all the entries in ⋃v∈NcΦc,m,v according to their reliability savings If the top k entries are contained in one subtree of cthen Replace the entry αk,βk by the second reliability saving path passing through c Else Choose the top k entries of ⋃v∈NcΦc,m,v and construct the induced subtree Λ c End If Calculate the reliability sum of Λc R S ∗ = m a x R S ∗ , R S Λ c S ∗ = Λ c, where RS∗=RSΛc End For EndFigure 5
A rooted tree with rootv2 and c is an internal vertex.LetΠ=v1,v2,…,vk⊆Can_Set_Lvsc,m be the set of top ranked vertices which are candidate to be the k leaves of the tree-shaped facility rooted at c. If the vertices of the set Π are not contained in one table Φc,m,j, then the induced subtree Π is a rooted reliable k,h-tree core of Tc. If the set Π is contained in one subtree of c, for example, the subtree attached to the vertex u through the edge c,uFor eachS⊆Can_Set_Lvsc, note that, for any S⊆Can_Set_Lvsc, let ΘS be S∪c which is a rooted subtree with S leaves and root c. Let ϝ=S:S⊆Can_Set_Lvsc,S=k.We now verify the correctness of the proposed algorithm. The next lemma is the key in proving Theorem22.Lemma 21.
IfΞ=a1,a2,…,ak-1,ak, then RSΘΞ=maxS∈ϝRSΘS.Proof.
Suppose thatQ=a1,a2,…,ak-1,b⊆Can_Set_Lvsc, where ΘQ has the maximum reliability sum, i.e.,RSΘQ=maxS∈ϝRSΘS. Let s∈VΘQ such that b and ak∈Can_Set_Lvsc are a descendant vertices of s and assume that s is dominated by ak,i.e.,Δak=s. Consider Q′=Q\b∪ak, then ΘQ′=ΘQ\Pw,b∪Ps,ak, where w is a child vertex of s on the path Ps,b. Hence,(52)RSΘQ′=RSΘQ-δαs,Ps,b+δαs,Ps,ak
Sinces is dominated by ak, then δαs,Ps,ak≥δαs,Ps,b, then(53)RSΘQ′≥RSΘQ which contradicts the assumption that RSΘQ is the maximum reliability sum.
Suppose thats is not dominated by ak and b is not a descendant vertex of s but ak is still a descendant vertex of s. Then, δαs,Ps,ak≥Ωak≥Ωb. Let Q′=Q\b∪ak. Then, we have(54)RSΘQ′=RSΘQ-δαfΔb,PfΔb,b+δαs,Ps,ak≥RSΘQ which is again a contradiction.The correctness of the proposed algorithm for finding the reliable tree core is summerized in the following theorem.Theorem 22.
For eachc∈Γ1∪Γ2, the proposed algorithm correctly finds the subtree Λc which is the reliable k,h-tree core of the tree Tc.Proof.
Let(55)ϝ∗=S:S∈ϝ,S⊈VTucforanyu∈Nc
Note thatϝ∗⊆ϝ, Λc∈ϝ∗ and for any S∈ϝ∗,S and ΘS are the same.
Suppose thata1∈VTuc, where u∈Nc. Let t be the smallest integer such that at∉VTuc. If t≤k, then Λc=a1,a2,…,ak. Since ϝ∗⊆ϝ and by Lemma 21, we obtain(56)RSΛc=max⁡RSΘSS∈ϝ≥max⁡RSSS∈ϝ∗ This proves the theorem for the case t≤k.
Consider the case in whicht>k. In this case Λc=Θa1,a2,…,ak-1∪Pc,at. Hence,(57)RSΛc=RSΘa1,a2,…,ak-1+δαc,Pc,at Consider a fixed S∈ϝ∗, and for any s∈S\VTuc, let S′=S\s. Then S=ΘS′∪PfΔs,s. Hence,(58)RSS≤RSΘS′+δαc,Pc,s
From Lemma21a1,a2,…,ak-1 maximizes RSΘA for all A⊆Can_Set_Lvsc of k-1 candidates. Hence, RSa1,a2,…,ak-1≥RSΘS′. By definition of t, we have δαc,Pc.at≥δαc,Pc,s. Therefore, (59)RSΛc=RSΘa1,a2,…,ak-1+δαc,Pc,at≥RSΘS′+δαc,Pc,s≥RSS which completes the proof of the theorem.Based on the algorithm presented by Wang et al. [7], the time complexity for the subroutine which determines the table Φ is Olkn. The time required for constructing Λc from Φ is OkNc. A reliable k,l-tree core is the subtree Λc that maximizes RSΛc over all c∈Γ1∪Γ2. By using the values in Φ, the value of the reliability sum RSΛc for every c∈Γ1∪Γ2 can be computed by Lemma 17 or Lemma 18. Therefore, the time complexity of constructing a reliable k,l-tree core from the table Φ is Olkn.Theorem 23.
The time complexity of the reliablek,l-tree core algorithm is Olkn


## 5. Numerical Example

In this section, a numerical example to illustrate the proposed algorithm is considered. A tree network withn=40 vertices and E=39 edges is depicted in Figure 6. The operational probabilities, shown on the arcs, are generated randomly in the interval 0,1. Γ1 is the set of centers of all paths of even lengths; in Table 2 a set of paths of length 6 are considered and the tree is rooted at the centers of these paths. Hence, the set Λc is constructed using the proposed algorithm and the optimal subtree Λc which is a reliable 4,3-tree core is obtained. The last column of the Table 2 is the reliability sum of the located subtree Λc. Also, Table 3 considered the case of odd length paths; the paths are centered at the middle edges, where each middle edge is contracted into a single vertex. Similar to the even length paths of Table 2, Table 3 presents a reliable 4,3-tree core with odd length diameters.Table 2
Some paths of length 6, their centers, the induced subtrees with maximum reliability saving, and the reliability sum of each subtree.
PathPu,v Rootc∈Γ1 Induced subtreeΛc R Λ c (5,12),(2,5),(1,2),(1,3),(3,7),(7,15) 1 14,15,17,20 24.8535  (6,14),(2,6),(1,2),(1,3),(3,8),(8,17) 1 14,15,17,20 24.8535  (10,18),(4,10),(1,4),(1,2),(2,6),(6,14) 1 14,15,17,20 24.8535  (14,25),(6,14),(2,6),(2,5),(5,13),(13,23) 2 25,7 , 8,11 24.1866  (20,30),(11,20),(4,11),(4,10),(10,18),(18,28) 4 6,7 , 8,30 22.7734  (22,31),(13,22),(5,13),(2,5),(1,2),(1,3) 5 32,2 , 3,12 21.9252  (25,34),(14,25),(6,14),(2,6),(1,2),(1,4) 6 13,3 , 4,34 20.9972  (37,27),(17,27),(8,17),(3,8),(1,3),(1,2) 8 2,4 , 15,37 17.8788  (39,29),(20,29),(11,20),(4,11),(1,4),(1,2) 11 2,3 , 19,40 19.8332  (40,30),(20,30),(11,20),(4,11),(1,4),(1,3) 11 2,3 , 19,40 19.8332  (22,13),(5,13),(2,5),(1,2),(1,3),(3,7) 2 25,7 , 8,11 24.1866  (17,26),(8,17),(3,8),(1,3),(1,2),(2,5) 3 5,10,11 19.1950  (18,28),(10,18),(4,10),(1,4),(1,2),(2,5) 4 6,7 , 8,30 22.7734  (22,31),(13,22),(5,13),(2,5),(2,6),(6,14) 5 32,2 , 3,12 21.9252  (25,34),(14,25),(6,14),(2,6),(2,5),(5,12) 6 13,3 , 4,34 20.9972Table 3
Some paths of length 7, their centers, the induced subtrees with maximum reliability saving, and the reliability sum of each subtree.
PathP(u,v) Roote∈Γ2 Induced subtreeΛc R(Λc) (3,7),(1,3),(1,2),(2,6),(6,14),(14,25),(25,34) ( 2,6 ) 34,7 , 8,11 23.5746 (4,10),(1,4),(1,2),(2,6),(6,14),(14,25),(25,35) ( 2,6 ) 34,7 , 8,11 23.5746 (4,11),(1,4),(1,2),(2,6),(6,14),(14,25),(25,34) ( 2,6 ) 34,7 , 8,11 23.5746 (5,12),(2,5),(1,2),(1,4),(4,10),(10,18),(18,28) ( 1,4 ) 14,15,16,29 23.2456 (8,17),(3,8),(1,3),(1,4),(4,11),(11,20),(20,30) ( 1,4 ) 14,15,16,29 23.2456 (6,14),(2,6),(1,2),(1,4),(4,10),(10,18),(18,28) ( 1,4 ) 14,15,16,29 23.2456 (17,26),(8,17),(3,8),(1,3),(1,4),(4,11),(11,21) ( 1,3 ) 13,14,20,21 22.7339 (17,26),(8,17),(3,8),(1,3),(1,4),(4,11),(11,20) (1,3) 13,14,20,21 22.7339 (17,27),(8,17),(3,8),(1,3),(1,4),(4,10),(10,19) (1,3) 13,14,20,21 22.7339Figure 6
A tree example on which the proposed algorithm is applied where the edge labels are the operational probabilities.


## 6. Summary and Conclusions

In this paper, we considered the problem of optimally locating a service facility in a tree network with unreliable edges. The service facility considered in this study is an extensive facility or a connected structure which is a special type of subgraph. We considered the location of a tree-shaped (subgraph) facility problem. This tree-shaped facility is a conditional extensive facility, where the constraint is to set a limit to the diameter of the selected facility. So, given two parametersk and l, the objective is to locate a reliable k,l-tree core which is a subtree with a diameter ≤l and having k leaves such that the sum of the reliabilities from all the vertices of the tree network to this facility is maximized. The objective of the problem is to maximize the expected number of nodes reachable by operational paths from the located site. An Olkn time complexity algorithm is presented based on a modifications to the algorithm developed by Wang et al. [7]. Computational results are provided.For a future research, the following problems can be considered:(i)
The location of a reliablek,l-tree core facility in a tree network with unreliable edges under the condition that existing facilities are already located.(ii)
The biobjective reliable central-mediank,l-tree core facility problem on tree networks with unreliable edges should be considered. In this problem the two criteria maximin and maxisum will be considered simultaneously and find the set of all the Pareto-Optimal paths.(iii)
Another extension is the multifacility reliable extensive facility network location problem. This problem seeks the location of more than one of tree-shaped facilities in such a way that it maximizes the sum of the reliabilities between nodes and new facilities.



---

*Source: 9520324-2019-08-21.xml*