Premium
Minimizing the makespan in multiserver network restoration problems
Author(s) -
Averbakh Igor
Publication year - 2017
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.21750
Subject(s) - server , computer science , node (physics) , enhanced data rates for gsm evolution , computer network , time complexity , point (geometry) , mathematical optimization , mathematics , algorithm , artificial intelligence , engineering , geometry , structural engineering
Suppose that a destroyed network needs to be restored by a number of servers (construction crews) that are initially located at some nodes of the network (depots). Each server can restore one unit of length of the network per unit of time. When several servers are simultaneously working at the same point, their restoration speeds combine additively. The servers can travel within the already restored part of the network with infinite speed, which means that travel times are negligible with respect to construction times. It is required to minimize the time when each node becomes connected to at least one of the depots. We show that the problem is strongly NP‐hard on general networks, and present fast polynomial algorithms for trees and cactus networks which are connected networks where each node and each edge belong to at most one cycle. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(1), 60–68 2017