@article {14957,
	title = {Efficient algorithms for list ranking and for solving graph problems on the hypercube},
	journal = {Parallel and Distributed Systems, IEEE Transactions on},
	volume = {1},
	year = {1990},
	month = {1990/01//},
	pages = {83 - 90},
	abstract = {A hypercube algorithm to solve the list ranking problem is presented. Let <e1>n</e1> be the length of the list, and let <e1>p</e1> be the number of processors of the hypercube. The algorithm described runs in time O(<e1>n</e1>/<e1>p</e1>) when <e1>n</e1>= Omega;(<e1>p</e1> <sup>1+ epsi;</sup>) for any constant epsi; gt;0, and in time O(<e1>n </e1> log <e1>n</e1>/<e1>p</e1>+log<sup>3</sup> <e1>p</e1>) otherwise. This clearly attains a linear speedup when <e1>n</e1>= Omega;(<e1>p</e1> <sup>1+ epsi;</sup>). Efficient balancing and routing schemes had to be used to achieve the linear speedup. The authors use these techniques to obtain efficient hypercube algorithms for many basic graph problems such as tree expression evaluation, connected and biconnected components, ear decomposition, and st-numbering. These problems are also addressed in the restricted model of one-port communication},
	keywords = {algorithm;hypercube, algorithms;graph, algorithms;linear, algorithms;sorting;, balancing;one-port, basic, communication;sorting;st-numbering;tree, complexity;graph, components;ear, decomposition;graph, evaluation;computational, Expression, graph, problems;biconnected, problems;hypercube, ranking;load, speedup;list, theory;parallel},
	isbn = {1045-9219},
	doi = {10.1109/71.80127},
	author = {Ryu,K. W. and JaJa, Joseph F.}
}
@conference {15199,
	title = {Efficient parallel algorithms for testing connectivity and finding disjoint s-t paths in graphs},
	booktitle = {Foundations of Computer Science, 1989., 30th Annual Symposium on},
	year = {1989},
	month = {1989/11/01/oct},
	pages = {288 - 293},
	abstract = {An efficient parallel algorithm for testing whether a graph <e1>G </e1> is <e1>K</e1>-vertex connected, for any fixed <e1>k</e1>, is presented. The algorithm runs in <e1>O</e1>(log <e1>n</e1>) time and uses <e1>nC</e1>(<e1>n</e1>,<e1>m</e1>) processors on a concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM), where <e1>n </e1> and <e1>m</e1> are the number of vertices and edges of <e1>G</e1> and <e1>C</e1>(<e1>n</e1>,<e1>m</e1>) is the number of processors required to compute the connected components of <e1>G</e1> in logarithmic time. An optimal speedup algorithm for computing connected components would induce an optimal speedup algorithm for testing <e1>k </e1>-vertex connectivity, for any <e1>k</e1> gt;4. To develop the algorithm, an efficient parallel algorithm is designed for the following disjoint <e1>s</e1>-<e1>t</e1> paths problem: Given a graph <e1>G</e1> and two specified vertices <e1>s</e1> and <e1>t</e1>, find <e1>k</e1>-vertex disjoint paths between <e1>s</e1> and <e1>t</e1>, if they exist. If no such paths exist, find a set of at most <e1>k</e1>-1 vertices whose removal disconnects <e1>s</e1> and <e1>t</e1>. The parallel algorithm for this problem runs in <e1>O</e1>(log <e1>n</e1>) time using <e1>C</e1>(<e1>n</e1>,<e1>m</e1>) processors. It is shown how to modify the algorithm to find <e1>k</e1>-edge disjoint paths, if they exist. This yields an efficient parallel algorithm for testing whether a graph <e1>G</e1> is <e1>k</e1>-edge connected, for any fixed <e1>k</e1>. The algorithm runs in <e1>O</e1>(log <e1>n</e1>) time and uses <e1>nC </e1> (<e1>n</e1>,<e1>n</e1>) processors on a CRCW PRAM. Again, an optimal speedup algorithm for computing connected components would induce an optimal speedup algorithm for testing <e1>k</e1>-edge connectivity},
	keywords = {algorithm;parallel, algorithms;random-access, algorithms;testing, complexity;graph, connectivity;computational, connectivity;optimal, CRCW, disjoint, paths;graphs;k-edge, paths;k-vertex, PRAM;disjoint, s-t, speedup, storage;, theory;parallel},
	doi = {10.1109/SFCS.1989.63492},
	author = {Khuller, Samir and Schieber,B.}
}
@article {15011,
	title = {Parallel algorithms for planar graph isomorphism and related problems},
	journal = {Circuits and Systems, IEEE Transactions on},
	volume = {35},
	year = {1988},
	month = {1988/03//},
	pages = {304 - 311},
	abstract = {Parallel algorithms for planar graph isomorphism and several related problems are presented. Two models of parallel computation are considered: the CREW-PRAM model and the two-dimensional array of processors. The results include <e1>O</e1>( radic;<e1>n</e1>)-time mesh algorithms for finding a good separating cycle and the triconnected components of a planar graph, and for solving the single-function coarsest partitioning problem},
	keywords = {2D, algorithms;, algorithms;parallel, array;computational, array;CREW-PRAM, coarsest, complexity;graph, components;two-dimensional, COMPUTATION, graph, graph;planar, isomorphism;single-function, model;mesh, models;planar, partitioning, problem;triconnected, processor, theory;parallel},
	isbn = {0098-4094},
	doi = {10.1109/31.1743},
	author = {JaJa, Joseph F. and Kosaraju,S.R.}
}
