A distributed algorithm for knot detection in a distributed graph

D. Manivannan; M. Singhal

doi:10.1109/ICPP.2002.1040905

A distributed algorithm for knot detection in a distributed graph

D. Manivannan
, M. Singhal

Computer Science

Producción científica: Conference contribution › revisión exhaustiva

4 Citas (Scopus)

Resumen

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.

Idioma original	English
Título de la publicación alojada	Proceedings - International Conference on Parallel Processing, ICPP 2002
Editores	Tarek S. Abdelrahman
Páginas	485-492
Número de páginas	8
ISBN (versión digital)	0769516777
DOI	https://doi.org/10.1109/ICPP.2002.1040905
Estado	Published - 2002
Evento	International Conference on Parallel Processing, ICPP 2002 - Vancouver, Canada Duración: ago 18 2002 → ago 21 2002

Serie de la publicación

Nombre	Proceedings of the International Conference on Parallel Processing
Volumen	2002-January
ISSN (versión impresa)	0190-3918

Conference

Conference	International Conference on Parallel Processing, ICPP 2002
País/Territorio	Canada
Ciudad	Vancouver
Período	8/18/02 → 8/21/02

Nota bibliográfica

Publisher Copyright:
© 2002 IEEE.

ASJC Scopus subject areas

Software
General Mathematics
Hardware and Architecture

Acceder al documento

10.1109/ICPP.2002.1040905

Otros archivos y enlaces

Citar esto

@inproceedings{1badd0c1aae5478e92b58dca701fe48b,

title = "A distributed algorithm for knot detection in a distributed graph",

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.",

keywords = "Application software, Buffer storage, Clustering algorithms, Computer science, Database systems, Detection algorithms, Distributed algorithms, Packet switching, Switches, System recovery",

author = "D. Manivannan and M. Singhal",

note = "Publisher Copyright: {\textcopyright} 2002 IEEE.; International Conference on Parallel Processing, ICPP 2002 ; Conference date: 18-08-2002 Through 21-08-2002",

year = "2002",

doi = "10.1109/ICPP.2002.1040905",

language = "English",

series = "Proceedings of the International Conference on Parallel Processing",

pages = "485--492",

editor = "Abdelrahman, \{Tarek S.\}",

booktitle = "Proceedings - International Conference on Parallel Processing, ICPP 2002",

}

Manivannan, D & Singhal, M 2002, A distributed algorithm for knot detection in a distributed graph. En TS Abdelrahman (ed.), Proceedings - International Conference on Parallel Processing, ICPP 2002., 1040905, Proceedings of the International Conference on Parallel Processing, vol. 2002-January, pp. 485-492, International Conference on Parallel Processing, ICPP 2002, Vancouver, Canada, 8/18/02. https://doi.org/10.1109/ICPP.2002.1040905

A distributed algorithm for knot detection in a distributed graph. / Manivannan, D.; Singhal, M.
Proceedings - International Conference on Parallel Processing, ICPP 2002. ed. / Tarek S. Abdelrahman. 2002. p. 485-492 1040905 (Proceedings of the International Conference on Parallel Processing; Vol. 2002-January).

Producción científica: Conference contribution › revisión exhaustiva

TY - GEN

T1 - A distributed algorithm for knot detection in a distributed graph

AU - Manivannan, D.

AU - Singhal, M.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - Application software

KW - Buffer storage

KW - Clustering algorithms

KW - Computer science

KW - Database systems

KW - Detection algorithms

KW - Distributed algorithms

KW - Packet switching

KW - Switches

KW - System recovery

UR - https://www.scopus.com/pages/publications/0242537465

UR - https://www.scopus.com/pages/publications/0242537465#tab=citedBy

U2 - 10.1109/ICPP.2002.1040905

DO - 10.1109/ICPP.2002.1040905

M3 - Conference contribution

AN - SCOPUS:0242537465

T3 - Proceedings of the International Conference on Parallel Processing

SP - 485

EP - 492

BT - Proceedings - International Conference on Parallel Processing, ICPP 2002

A2 - Abdelrahman, Tarek S.

T2 - International Conference on Parallel Processing, ICPP 2002

Y2 - 18 August 2002 through 21 August 2002

ER -

A distributed algorithm for knot detection in a distributed graph

Resumen

Serie de la publicación

Conference

Nota bibliográfica

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto