1. J.K. Cullum and R.A. Willoughby. Lanczos algorithms for Large Symmetric Eigenvalue Computations. Volume 1, Theory. Birkhäuser, 1985.
   

   @book{ CullumWilloughby1985,
   author = {J.K. Cullum and R.A. Willoughby},
   title = {Lanczos algorithms for Large Symmetric Eigenvalue Computations. Volume 1, Theory},
   publisher = {Birkh\"auser},
   loaction = {Boston, MA, USA},
   year = {1985},
   
   }
   

1. Baruch Awerbuch. A new distributed depth-first-search algorithm. Information Processing Letters, 20(3):147-150, 1985. [PDF] Keyword(s): Depth-first search, Distributed system, communication graph. Abstract:

   This paper presents a new distributed Depth-First-Search (DFS) algorithm for an asynchronous communication network, whose communication and time complexities are $O(|E|)$ and $O(|V|)$, respectively. The output of the algorithm is the DFS tree, kept in a distributed fashion. The existing algorithm, due to Cheung (1983), requires $O(|E|)$ both in communication and time complexities.

   
   

   @Article{AwerbuchDFS85,
   author = {Baruch Awerbuch},
   title = {A new distributed depth-first-search algorithm},
   journal = {Information Processing Letters},
   volume = {20},
   number = {3},
   year = {1985},
   pages = {147--150},
   publisher = {Elsevier North-Holland, Inc.},
   keywords = {Depth-first search; Distributed system; communication graph},
   pdf = {PAPERS/AwerbuchDFS85.pdf},
   abstract = {This paper presents a new distributed Depth-First-Search (DFS) algorithm for an asynchronous communication network, whose communication and time complexities are $O(|E|)$ and $O(|V|)$, respectively. The output of the algorithm is the DFS tree, kept in a distributed fashion. The existing algorithm, due to Cheung (1983), requires $O(|E|)$ both in communication and time complexities.} 
   }
   




2. A. Frieze and G. Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics, 10:57-77, 1985.
   

   @article{Frieze85,
   author = {Frieze, A. and Grimmett, G.},
   title = "The shortest-path problem for graphs with random arc-lengths",
   journal = "Discrete Applied Mathematics",
   volume = "10",
   pages = {57--77},
   year = "1985" 
   }
   




3. Refael Hassin and Eitan Zemel. On Shortest Paths in Graphs with Random Weights. Mathematics of Operations Research, 10(4):557-564, November 1985.
   

   @article{Hassin85,
   author = {Refael Hassin and Eitan Zemel},
   title = "On Shortest Paths in Graphs with Random Weights",
   journal = {Mathematics of Operations Research},
   volume = "10",
   number = "4",
   month = "November",
   year = "1985",
   pages = {557--564} 
   }
   




4. John H. Reif. Depth-First Search is Inherently Sequential. Information Processing Letters, 20(5):229-234, June 1985. [PDF] Keyword(s): Depth-first search, parallel computation, polynomial time complete. Abstract:

   This paper concerns the computational complexity of depth-first search. Suppose we are given a rooted graph G with fixed adjacency lists and vertices u, v. We wish to test if u is first visited before v in depth-first search order of G. We show that this problem, for undirected and directed graphs, is complete in deterministic polynomial time with respect to deterministic log-space reductions. This gives strong evidence that depth-first search ordering can be done neither in deterministic space $(log n)^c$ nor in parallel time $(log n)^c$, for any constant $c > 0$.

   
   

   @Article{ReifDFS85,
   author = {John H. Reif},
   title = {Depth-First Search is Inherently Sequential},
   journal = {Information Processing Letters},
   year = 1985,
   volume = 20,
   number = 5,
   pages = {229--234},
   month = {June},
   pdf = {PAPERS/ReifDFS85.pdf},
   abstract = {This paper concerns the computational complexity of depth-first search. Suppose we are given a rooted graph G with fixed adjacency lists and vertices u, v. We wish to test if u is first visited before v in depth-first search order of G. We show that this problem, for undirected and directed graphs, is complete in deterministic polynomial time with respect to deterministic log-space reductions. This gives strong evidence that depth-first search ordering can be done neither in deterministic space $(log n)^c$ nor in parallel time $(log n)^c$, for any constant $c > 0$.},
   keywords = {Depth-first search; parallel computation; polynomial time complete} 
   }
   




5. R. E. Tarjan and U. Vishkin. An Efficient Parallel Biconnectivity Algorithm. SIAM J. Comput., 14(4):862-874, 1985. Keyword(s): Biconnected components.
   

   @Article{TarjanBiconnected85,
   author = {R. E. Tarjan and U. Vishkin},
   title = {An Efficient Parallel Biconnectivity Algorithm},
   journal = {SIAM J. Comput.},
   year = 1985,
   volume = 14,
   number = 4,
   pages = {862--874},
   keywords = {Biconnected components} 
   }
   

1. Gary L. Miller and John H. Reif. Parallel tree contraction and its application. In : Proceedings of the 26th Annual Symposium on Foundations of Computer Science, Washington, DC, USA, pages 478-489, 1985. IEEE. ISBN: 0-8186-0844-4. [doi:http://dx.doi.org/10.1109/SFCS.1985.43]
   

   @inproceedings{Miller85,
   author = {Miller, Gary L. and Reif, John H.},
   title = {Parallel tree contraction and its application},
   booktitle = {: Proceedings of the 26th Annual Symposium on Foundations of Computer Science},
   year = {1985},
   isbn = {0-8186-0844-4},
   pages = {478--489},
   doi = {http://dx.doi.org/10.1109/SFCS.1985.43},
   publisher = {IEEE},
   address = {Washington, DC, USA},
   
   }
   

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