On Gazit and Miller's parallel algorithm for planar separators

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On Gazit and Miller's parallel algorithm for planar separators: achieving greater efficiency through random sampling

Full text

Pdf (838 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures table of contents

Velen, Germany

Pages: 43 - 49

Year of Publication: 1993

ISBN:0-89791-599-2

Author

Philip Klein

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 19, Citation Count: 1

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/165231.165237 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	Bonnie Berger , John Rompel , Peter W. Shor, Efficient NC algorithms for set cover with applications to learning and geometry, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.454-477, December 1994, Research Triangle Park, North Carolina, United States
	2	V. Chv#tal, "A greedy heuristic for the set-covering problem," Math. of OR Vol. 4, No. 3, pp. 233-235 (1979).
	3	Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
	4	H. Gazit and G. L. Miller, "An O(v#logn) optimal parallel algorithm for a separator in planar graphs," manuscript.
	5	H. Gazit and G. L. Miller, "A parallel algorithm for finding a separator in planar graphs," FOCS 87, pp. 238-248.
	6	H. Gazit and G.L. Miller, "A Deterministic Parallel Algorithm for Finding a Separator in Planar Graphs," manuscript.
	7	Mark Goldberg , Thomas Spencer, Constructing a maximal independent set in parallel, SIAM Journal on Discrete Mathematics, v.2 n.3, p.322-328, August 1989 [doi>10.1137/0402028]
	8	D. S. Johnson, "Approximation algorithms for Combinatorial Problems," J. Comp. System. Sci., 9, pp. 256- 278 (1974).
	9	Richard M. Karp, Probabilistic recurrence relations, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.190-197, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103443]
	10	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 [doi>10.1145/129712.129785]
	11	P. N. Klein and S. Subramanian, "An efficient parallel approximation schemes for planar shortest paths," manuscript (1993).
	12	L. Lov#z, "On the Ratio of Optimal Integral and Fractional Covers," Discrete Math., 13, pp. 383-390 (1975).
	13	Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
	14	Michael Luby, Removing randomness in parallel computation without a processor penalty, Journal of Computer and System Sciences, v.47 n.2, p.250-286, Oct. 1993 [doi>10.1016/0022-0000(93)90033-S]
	15	C. Leiserson "Area-efficient graph layouts (for VLSI)," FOCS 80, pp. 270-281.
	16	K. J. Lipton and 1#. E. Tarjan, ~'A separator theorem for planar graphs," SIAM J. Appl. Math. 36, pp. 177-189 (1979).
	17	R.J. Lipton, D. J. Rose, and 1#. E. Tarjem, "Generalized nested dissection," SIAM J. on Numerical Analysis 3, pp. 57-67 (1983).
	18	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]
	19	Gary L. Miller , Shang-Hua Teng , Stephen A. Vavasis, A unified geometric approach to graph separators, Proceedings of the 32nd annual symposium on Foundations of computer science, p.538-547, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185417]
	20	V. Pan and J. H. Reif, "Extension of parallel nested dissection algorithm to the path algebra problems," Computer Science Dept. TR-85-9, State University of New York at Albany (1985).
	21	Jeffrey D. Ullman , Mihalis Yannakakis, High probability parallel transitive-closure algorithms, SIAM Journal on Computing, v.20 n.1, p.100-125, Feb. 1991 [doi>10.1137/0220006]