A Distributed Graph Algorithm: Knot Detection

Publisher Website
Google Scholar
Abstract
A v e r t e x vi i n a d i r e c t e d g r a p h is i n a k n o t i f f o r e v e r y v e r t e x vj r e a c h a b l e f r o m vi, vi is r e a c h a b l e f r o m vj. C h a n g [2] s h o w s t h a t k n o t is a u s e f u l c o n c e p t i n d e a d l o c k d e t e c t i o n. D i j k s t r a [3] h a s p r o p o s e d a d i s t r i b u t e d a l g o r i t h m f o r d e t e c t i n g w h e t h e r a g i v e n p r o c e s s in a n e t w o r k o f p r o c e s s e s is i n a k n o t. H i s a l g o r i t h m is b a s e d o n h i s p r e v i o u s w o r k w i t h S c h o l t e n [4] o n t e r m i n a t i o n d e t e c t i o n o f d i f f u s i n g c o m-p u t a t i o n s. W e p r o p o s e a n a l g o r i t h m f o r k n o t d e t e c t i o n w h i c h is a l s o b a s e d o n [4] b u t is c o n c e p t u a l l y s i m p l e r. W e a l s o d i s c u s s t h e e x t e n s i o n s o f o u r a l g o r i t h m t o a m o r e g e n e r a l c l a s s o f p r o b l e m s.

This publication has 2 references indexed in Scilit: