Algorithms for parallel k-vertex connectivity and sparse certificates

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AP 90	B. Awerbuch and D. Peleg, "Network synchronization with polylogarithmic overhead," Proc. 31st Syrup. Found. Comp. Sc,. (1990), 514-522.
	B 78	Bela Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
	BGH 82	A. Borodin, J. yon zur Gathen and J. Hopcroft, "Fast parallel matrix and GCD computations", Proc. 23rd Symp. Found. Comp. Sc#. (19s#), 65-71.
	CM 88	J. Cheriyan , S. N. Maheshwari, Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, Journal of Algorithms, v.9 n.4, p.507-537, Dec. 1988 [doi>10.1016/0196-6774(88)90015-6]
	CT 90	Joseph Cheriyan , Ramakrishna Thurmella, On determining vertex connectivity, University of Maryland at College Park, College Park, MD, 1990
	CT 90b	J. Claeriyan and R. Thurimella, "Finding sparse spanning subgraphs efficiently", Preprint, Aug. 1990.
	CV 86	R. Cole and U. Vishkin, "Approximate and exact parallel scheduling with applications to list, tree, and graph problems," Proc. #7th Syrup. Found. Comp. Sci. (1986), 478-491.
	D 82	D. Dolev, "The Byzantine generals strike again," J. Algorithms 3 (1982), 14-30.
	E 75	S. Even, "An algorithm for determining whether the connectivity of a graph is at least k," SIAM J. Computing 4 (1975), 393-396.
	E 79	S. Even, Graph Algomthms, Computer Science Press, Potomac, Md., 1979.
	FRT 89	Donald S. Fussell , Vijaya Ramachandran , Ramakrishna Thurimella, Finding Triconnected Components by Local Replacements, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.379-393, July 11-15, 1989
	H 87	V. Hadzilacos, "Connectivity requirements for Byzantine agreement under restricted types of failures," Distributed Computing 2 (1987), 95- 103.
	G 80	Z. Galil, "Finding the vertex connectivity of graphs," SIAM J. Computing 9 (1980), 197- 199.
	GJ 79	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	IR 88	Alon Itai , Michael Rodeh, The multi-tree approach to reliability in distributed networks, Information and Computation, v.79 n.1, p.43-59, October 1988 [doi>10.1016/0890-5401(88)90016-8]
	KR 87	Arkady Kanevsky , Vijaya Ramachandran, Improved algorithms for graph four-connectivity, Journal of Computer and System Sciences, v.42 n.3, p.288-306, June 1991 [doi>10.1016/0022-0000(91)90004-O]
	KS 89	S. Khuller and B. Schieber, "Efficient parallel algorithms for testing connectivity and finding disjoint s-t paths in graphs", Proc. 80th Syrup. Found. Comp. Sci. (1989), 288-293.
	LLW 88	N. Linial, L. Lov~sz and A. Wigderson, "Rubber bands, convex embeddings and graph connectivity," Combinatorica 8 (1988), 91-102.
	Lo 73	L. Lov~sz, "Connectivity in digraphs", J. Combinatorial Theory (B)15 (1973), 174-177.
	MVV 87	K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
	NI 90	H. Nagamochi and T. Ibaraki, "Linear time algorithms for finding a sparse k-connected spanning subgraph of a k-connected graph", Algorithmica, to appear.
	NI 90b	Hiroshi Nagamochi , T. Ibaraki, Computing edge-connectivity in multiple and capacitated graphs, Proceedings of the international symposium on Algorithms, p.12-20, August 1990, Tokyo, Japan
	T 89	Ramakrishna Thurimella , Donald S. Fussell, Techniques for the design of parallel graph algorithms, 1989
	TV 84	R.E. Tarjan and U. Vishkin, "An efficient paraim biconnectivity algorithm," SIAM J. Computing 14 (1984), 862-874.