Original scientific paper
https://doi.org/10.20532/cit.2019.1004754
An Algorithm for Finding Two Node-Disjoint Paths in Arbitrary Graphs
Mehmet Hakan Karaata
; Department of Computer Engineering, Kuwait University
Abstract
Given two distinct vertices (nodes) source s and target t of a graph G = (V, E), the two node-disjoint paths problem is to identify two node-disjoint paths between s ∈ V and t ∈ V. Two paths are node-disjoint if they have no common intermediate vertices. In this paper, we present an algorithm with O(m)-time complexity for finding two node-disjoint paths between s and t in arbitrary graphs where m is the number of edges. The proposed algorithm has a wide range of applications in ensuring reliability and security of sensor, mobile and fixed communication networks.
Keywords
disjoint paths, distributed systems, fault tolerance, network routing, security
Hrčak ID:
237989
URI
Publication date:
7.5.2020.
Visits: 848 *