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. The 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 or 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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings - International Conference on Parallel Processing, ICPP 2002 |
| Editors | Tarek S. Abdelrahman |
| Pages | 485-492 |
| Number of pages | 8 |
| ISBN (Electronic) | 0769516777 |
| DOIs | |
| State | Published - 2002 |
| Event | International Conference on Parallel Processing, ICPP 2002 - Vancouver, Canada Duration: Aug 18 2002 → Aug 21 2002 |
Publication series
| Name | Proceedings of the International Conference on Parallel Processing |
|---|---|
| Volume | 2002-January |
| ISSN (Print) | 0190-3918 |
Conference
| Conference | International Conference on Parallel Processing, ICPP 2002 |
|---|---|
| Country/Territory | Canada |
| City | Vancouver |
| Period | 8/18/02 → 8/21/02 |
Bibliographical note
Publisher Copyright:© 2002 IEEE.
Keywords
- Application software
- Buffer storage
- Clustering algorithms
- Computer science
- Database systems
- Detection algorithms
- Distributed algorithms
- Packet switching
- Switches
- System recovery
ASJC Scopus subject areas
- Software
- General Mathematics
- Hardware and Architecture