Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs

Full text

Pdf (1.38 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 181 - 192

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

M.-Y. Kao	Department of Computer Science, Duke University, Durham, North Carolina
P. N. Klein	Department of Computer Science, Brown University, Providence, Rhode Island

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 21, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/100216.100237 What is a DOI?

REFERENCES

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.

	1	A. AGGARWAL AND R. ANDERSON, A random NC algorithm for depth first search, Combinatorica, 8 (1988), pp. 1- 12.
	2	A. Aggarwal , R. J. Anderson , M.-Y. Kao, Parallel depth-first search in general directed graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.297-308, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73035]
	3	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	4	Richard J. Anderson , Gary L. Miller, Deterministic Parallel List Ranking, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.81-90, June 28-July 01, 1988
	5	John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
	6	Richard Cole , Uzi Vishkin, Optimal Parallel Algorithms for Expression Tree Evaluation and List Ranking, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.91-100, June 28-July 01, 1988
	7	D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
	8	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	9	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
	10	D. Fussell , R. Thurimella, Separation pair detection, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	11	H. GAZIT AND G. L. MILLER, A parallel algorithm for finding a separator in planar graphs, FOGS, 1987, pp. 238- 248.
	12	Hillel Gazit , Gary L. Miller, An improved parallel algorithm that computes the BFS numbering of a directed graph, Information Processing Letters, v.28 n.2, p.61-65, June 24, 1988 [doi>10.1016/0020-0190(88)90164-0]
	13	F. HARARY, Graph Theory, Addlson-Wesley, 1969.
	14	Xin He , Yaacov Yesha, A nearly optimal parallel algorithm for constructing depth first spanning trees in planar graphs, SIAM Journal on Computing, v.17 n.3, p.486-491, June 1988 [doi>10.1137/0217028]
	15	J. JA'JA AND S. KOSARAJU, Parallel algorithms }or planar graphs and related problems, IEEE Trans. Circuits and Systems, 35 (1988), pp. 304-311.
	16	A. KANEVSKY AND V. RAMACHANDRAN, Improved algorithms for graph four-connectivity, FOCS, 1987, pp. 252-259.
	17	M. Kao, All graphs have cycle separators and planar directed depth-first search is in DNC (preliminary version), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	18	_____, Linear-processor NC algorithms for planar directed graphs I: strongly connected components. Submitted, 1989.
	19	M.Y. KAO AND G. E. SHANNON) Linear-processor NC algorithms for planar directed graphs II: directed spanning trees. Submitted, 1989.
	20	M.-Y. Kao , G. E. Shannon, Local reorientation, global order, and planar topology, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.286-296, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73034]
	21	R. KARP AND V. RAMACHANDRAN) A survey o} parallel algorithms Jor shared-memory machines. To appear in the Handbook of Theoretical Computer Science, North- Holland.
	22	Philip N. Klein , John H. Reif, An efficient parallel algorithm for planarity, Journal of Computer and System Sciences, v.37 n.2, p.190-246, October 1988 [doi>10.1016/0022-0000(88)90006-2]
	23	S. Rao Kosaraju , Arthur L. Delcher, Optimal Parallel Evaluation of Tree-Structured Computations by Raking, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.101-110, June 28-July 01, 1988
	24	R. LIPTON AND R. TARJAN, A separator theorem for planar graphs, SIAM Journal on Algebraic and Discrete Methods, 36 (1979), pp. 177-189.
	25	L. Lovasz, Computing ears and branchings, FOGS, 1985, pp. 464-467.
	26	Y Maon , B Schieber , U Vishkin, Parallel ear decomposition search (EDS) and st-numbering in graphs, Proc. of the Aegean workshop on computing on VLSI algorithms and architectures, p.34-45, August 1986, Loutraki, Greece
	27	G. Miller , V. Ramachandran, A new graphy triconnectivity algorithm and its parallelization, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.335-344, January 1987, New York, New York, United States [doi>10.1145/28395.28431]
	28	G. MILLER AND J. REIF, Parallel tree contractions and its applications, STOC, 1985, pp. 478-489.
	29	Gary L Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, v.32 n.3, p.265-279, June 1986 [doi>10.1016/0022-0000(86)90030-9]
	30	G. L. MILLER AND J. NAOR, Flow in planar graphs with multiple sources and sinks, FOGS, 1989, pp. 112-117.
	31	V. PAN AND J. H. REIF, Extension o} parallel nested dissection algorithm to the path algebra problems, Tech. Rep. 9, Computer Science Department, State University of New York at Albany, 1985.
	32	_____, Fast and efficient solution of path algebra problems, Tech. Rep. 3, Computer Science Department, State University of New York at Albany, 1987.
	33	V. RAMACHANDRAN AND J. H. REIF, An optimal parallel 287.
	34	Vijaya Ramachandran , Uzi Vishkin, Efficient Parallel Triconnectivity in Logarithmic Time, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.33-42, June 28-July 01, 1988
	35	J. H. REIF, Depth-first search is inherently sequential, Inform. Process. Lett., 20 (1985), pp. 229-234.
	36	Y. SHILOACH AND U. VISHKIN, An O(logn) parallel con. nectivity algorithm, Journal of Algorithms, 3 (1982), pp. 57-67.
	37	Justin R Smith, Parallel algorithms for depth-first searches I. planar graphs, SIAM Journal on Computing, v.15 n.3, p.814-830, August 1986 [doi>10.1137/0215058]
	38	R. TARJAN, Depth-first search and linear graph algorithms, SIAM J. Comput., 1 (1972), pp. 146-160.
	39	R. Tamassia , J. S. Vitter, Optimal parallel algorithms for transitive closure and point location in planar structures, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.399-408, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72978]

CITED BY 5

	Stephen Guattery , Gary L. Miller, A contraction procedure for planar directed graphs, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.431-441, June 29-July 01, 1992, San Diego, California, United States
	Vijaya Ramachandran , Honghua Yang, An efficient parallel algorithm for the general planar monotone circuit value problem4, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.622-631, January 23-25, 1994, Arlington, Virginia, United States
	Edith Cohen, Efficient parallel shortest-paths in digraphs with a separator decomposition, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.57-67, June 30-July 02, 1993, Velen, Germany
	Philip N. Klein , S. Sairam, A parallel randomized approximation scheme for shortest paths, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.750-758, May 04-06, 1992, Victoria, British Columbia, Canada
	Warren J. Schudy, Finding strongly connected components in parallel using o(log²n) reachability queries, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany