Min-min edge-disjoint path pairs with constraints on common nodesMin-min edge-disjoint path pairs with constraints on common nodesS. Shan et al.

被引：0

作者：

Shanshan Shan ^{[1
]}

Shurong Zhang ^{[1
]}

Lin Chen ^{[2
]}

Dongyue Liang ^{[1
]}

Weihua Yang ^{[1
]}

Shuli Zhao ^{[3
]}

机构：

[1] Taiyuan University of Technology,College of Mathematics

[2] Macao Polytechnic University,Engineering Research Centre of Applied Technology on Machine Translation and Artificial Intelligence

[3] Henan Normal University,College of Mathematics and Statistics

来源：

The Journal of Supercomputing | / 81卷 / 5期

关键词：

Edge-disjoint path pairs; Min-min weight paths; Graph algorithms; Fault tolerance; Constraints on common nodes;

D O I：

10.1007/s11227-025-07064-6

中图分类号：

学科分类号：

摘要：

Finding edge-disjoint path pairs has been recognized as a vital issue in terms of the fault tolerance and survivability of networks. In many practical scenarios, in order to reduce standby and restart energy consumption and improve data transmission efficiency, we need to consider a constraint to control the delay difference of data transmission on each common node of two edge-disjoint paths. Meanwhile, a large number of common nodes tend to cause data congestion and increase the probability that faulty common nodes break two edge-disjoint paths. Based on these, we propose the problem of finding min-min edge-disjoint path pairs under the constraints of delay difference and the number of common nodes. To address the problem, we discretize each node according to its all processing time intervals to construct an equivalent problem in an auxiliary time digraph with delay division node sets. Then, we design conflicting node exclusion (CoNE) algorithm, a heuristic algorithm, using divide-and-conquer strategy on the conflicting node set. Finally, through extensive simulations, comparing with other related algorithms, we show that CoNE is significantly effective in large-scale networks.

引用