Proceedings International Conference on Parallel Processing
Download PDF

Abstract

Knot detection in a distributed graph is an important problem and finds applications in several areas such as packet switching, distributed simulation, and distributed database systems. This paper presents a distributed algorithm to efficiently detect the existence of a knot in a distributed graph. The algorithm requires 2e messages and a delay of 2(d+1) message hops to detect if a node in a distributed graph is in a knot (e is the number of edges in the reachable part of the distributed graph and d is its diameter). A significant advantage of this algorithm is that it not only detects if a node is in a knot but also finds exactly which nodes are involved in the knot.
Like what you’re reading?
Already a member?Sign In
Member Price
$11
Non-Member Price
$21
Add to CartSign In
Get this article FREE with a new membership!

Related Articles