1. K. B. Lakshmanan, N. Meenakshi, and K. Thulasiraman. A time-optimal message-efficient distributed algorithm for depth-first-search. Information Processing Letters, 25(2):103-109, 1987. [PDF] Keyword(s): Depth-first search. Abstract:

   In this paper we study the problem of distributed construction of a depth-first-search tree for an asynchronous communication network. First, we point out that any algorithm requires at least $2n−2$ time units and $2m$ messages in the worst case, where n and m are the number of nodes and the number of edges in the network, respectively. We then provide a modification to a recent algorithm due to Awerbuch (1985), and show that the new algorithm is time-optimal, while requiring less then $4m−(n−1)$ messages.

   
   

   @Article{LakshmananMeenakshiThulasiramanDFS87,
   author = {K. B. Lakshmanan and N. Meenakshi and K. Thulasiraman},
   title = {A time-optimal message-efficient distributed algorithm for depth-first-search},
   journal = {Information Processing Letters},
   volume = {25},
   number = {2},
   year = {1987},
   pages = {103--109},
   publisher = {Elsevier North-Holland, Inc.},
   keywords = {Depth-first search},
   pdf = {PAPERS/LakshmananMeenakshiThulasiramanDFS87.pdf},
   abstract = {In this paper we study the problem of distributed construction of a depth-first-search tree for an asynchronous communication network. First, we point out that any algorithm requires at least $2n−2$ time units and $2m$ messages in the worst case, where n and m are the number of nodes and the number of edges in the network, respectively. We then provide a modification to a recent algorithm due to Awerbuch (1985), and show that the new algorithm is time-optimal, while requiring less then $4m−(n−1)$ messages.} 
   }
   

1. Alok Aggarwal and Richard J. Anderson. A random NC algorithm for depth first search. In Proceedings of the nineteenth annual ACM conference on Theory of computing, pages 325-334, 1987. ACM Press. ISBN: 0-89791-221-7. [PDF] Keyword(s): Depth-first search, PRAM.
   

   @InProceedings{AggarwalAndersonDFS87,
   author = {Alok Aggarwal and Richard J. Anderson},
   title = {A random {NC} algorithm for depth first search},
   booktitle = {Proceedings of the nineteenth annual {ACM} conference on Theory of computing},
   year = {1987},
   isbn = {0-89791-221-7},
   pages = {325--334},
   location = {New York, New York, United States},
   publisher = {ACM Press},
   keywords = {Depth-first search, PRAM},
   pdf = {PAPERS/AggarwalAndersonDFS87.pdf},
   
   }
   




2. Jing-fu Jenq and Sartaj Sahni. All Pairs Shortest Paths on a Hypercube Multiprocessor. In Proceedings of the International Conference on Parallel Processing, pages 713-716, 1987.
   

   @InProceedings{Jenq87,
   author = {{Jing-fu} Jenq and Sartaj Sahni},
   title = {All Pairs Shortest Paths on a Hypercube Multiprocessor},
   booktitle = {Proceedings of the International Conference on Parallel Processing},
   year = {1987},
   pages = {713--716} 
   }
   

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All person copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Les documents contenus dans ces répertoires sont rendus disponibles par les auteurs qui y ont contribué en vue d'assurer la diffusion à temps de travaux savants et techniques sur une base non-commerciale. Les droits de copie et autres droits sont gardés par les auteurs et par les détenteurs du copyright, en dépit du fait qu'ils présentent ici leurs travaux sous forme électronique. Les personnes copiant ces informations doivent adhérer aux termes et contraintes couverts par le copyright de chaque auteur. Ces travaux ne peuvent pas être rendus disponibles ailleurs sans la permission explicite du détenteur du copyright.

This document was translated from BibT_EX by bibtex2html