An Algorithm for Finding Two Node-Disjoint Paths in Arbitrary Graphs | Zendy

Mehmet Hakan Karaata | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An Algorithm for Finding Two Node-Disjoint Paths in Arbitrary Graphs

Author(s) -

Mehmet Hakan Karaata

Publication year - 2020

Publication title -

journal of computing and information technology

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.169

H-Index - 27

eISSN - 1846-3908

pISSN - 1330-1136

DOI - 10.20532/cit.2019.1004754

Subject(s) - disjoint sets , computer science , node (physics) , floyd–warshall algorithm , graph , time complexity , algorithm , combinatorics , theoretical computer science , discrete mathematics , mathematics , shortest path problem , structural engineering , k shortest path routing , engineering

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research