Minsum node-disjoint paths with time-varying delay functions

Abstract

The fault tolerance of telecommunication networks is the ability to maintain service continuity in case of accident and attack. Designing disjoint paths to ensure fault tolerance of networks is regarded as one of the most important research problem. Especially in time-dependent networks which is used to the model that the weight of each link varies with time, answering shortest disjoint paths queries and plans in real time is considered to be one of major challenges in many industrial applications. Motivated by this observation, in the first in and first out (FIFO) time-varying network, we investigate the problem of finding two time-varying node-disjoint paths from the source to the destination with the departure time $t\in [0,T]$ such that the total time-varying delay of the paths is minimised. Based on the time-varying interlacing path in different time-intervals, we develop an effective algorithm to obtain the optimal solutions in time $O\left(n^2\alpha \right(T{)}^3)$.

Keywords:

• Node-disjoint paths
• time-varying networks
• Minsum
• fault tolerance

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work is supported by the National Natural Science Foundation of China (Grant Number 61502330) and Natural Science Foundation of Shanxi Province (Grant Number 201801D221193).