Network survivability has drawn certain interest in network optimization. However, the demand for full protection of a network is usually too restrictive. To overcome the limitation of geographical environments and to save network resources, we turn to establish backup networks allowing a few common nodes. It comes out the problem of finding k link-disjoint paths between a given pair of source and sink in a network such that the number of common nodes shared by at least two paths is bounded by a constant and the total link weight of all paths is minimized under the above constraints. For the case k = 2, where we have only one backup path, several fast algorithms have been developed in the literature. For the case k > 2, little results are known. In this paper, we first establish the NP-hardness of the problem with general k. Motivated by the situation that each node in a network may have a capability of multicasting, we also study a restricted version with one more requirement that each node can be shared by at most two paths. For the restricted version, we build an ILP model and design a fast algorithm by using the techniques of augmenting paths and splitting nodes. Furthermore, experimental results on synthetic and real networks show that our algorithm is effective in practice.
Published Date: 2020-06-02
Registration: ISSN 2374-3468 (Online) ISSN 2159-5399 (Print) ISBN 978-1-57735-835-0 (10 issue set)
Copyright: Published by AAAI Press, Palo Alto, California USA Copyright © 2020, Association for the Advancement of Artificial Intelligence All Rights Reserved