Premium
Location of facilities on a network subject to a single‐edge failure
Author(s) -
Eiselt Horst A.,
Gendreau Michel,
Laporte Gilbert
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220303
Subject(s) - vertex (graph theory) , combinatorics , enhanced data rates for gsm evolution , tree network , mathematics , greedy algorithm , set (abstract data type) , tree (set theory) , computer science , facility location problem , undirected graph , discrete mathematics , mathematical optimization , graph , time complexity , artificial intelligence , programming language
In this work, the following location problem is analyzed. Let N = (V,E) be an undirected connected simple network, where V is the vertex set, | V | = n and E is the edge set. There is a nonnegative demand w j associated with every vertex u j . It is assumed that every edge (u i ,u j ) has a probability of failure p ij and that failures can never occur on two edges simultaneously. The problem consists of locating p facilities on the network so that the total expected demand disconnected from the facilities is minimized. This problem occurs naturally in the fields of computer and telecommunications networks. A number of important results are proved. First, there always exists a solution in which all facilities are located at vertices. Second, the problem can always be solved optimally on the so‐called leaf‐tree associated with the network. Third, when p = 1, the problem is a 1‐median problem. When p > 1, there always exists an optimal solution for which all facilities are located at pendent vertices of the tree. Finally, when p > 2, the problem with p + 1 facilities can be solved in a greedy fashion, starting from a solution to the problem with p facilities. An exact algorithm for this problem is described. It can be executed in either O ( np + | E |) time or in O ( n log n + | E |) time. A numerical example is provided.