Minsum node-disjoint paths with time-varying delay functions. Issue 4 (4th July 2022)

• Record Type: Journal Article
• Authors: Xue, Xiaohong; Zhang, Shurong
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 37:Issue 4(2022)
• Page Start: 398
• Page End: 412
• Publication Date: 2022-07-04
• Subjects: Node-disjoint paths -- time-varying networks -- Minsum -- fault tolerance; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2021.2024537
• Languages: English
• ISSNs: 1744-5760

Abstract

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 ∈ [ 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 ( n 2 α ( T ) 3 ) .