An efficient parallel algorithm that finds independent sets of guaranteed size

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An efficient parallel algorithm that finds independent sets of guaranteed size

Full text

Pdf (800 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 219 - 225

Year of Publication: 1990

ISBN:0-89871-251-3

Authors

Mark Goldberg	Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York
Thomas H. Spencer	Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM-AGDM : SIAM AG Descrete Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 22, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

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

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.

	AA	A. Aggarwal , R. Anderson, A random NC algorithm for depth first search, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.325-334, January 1987, New York, New York, United States [doi>10.1145/28395.28430]
	ABI	Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
	BM	John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
	B	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	Co	R. Cole, Parallel merge sort, in Proc. 27th Annual Symposium on Foundation of Computer Science, (1986), pp. 511-516.
	Er	P. ErdSs, On Even Snbgraphs of Graphs (in Hungarian) Mat. Lapok., 18 (1964), pp. 283-288.
	Go	M. Goldberg, Parallel algorithms for three graph problems, Congr. Numer., 54 (1986), pp. 111- 121.
	GLR	M. Goldberg, S. Lath, and J. Roberts, Heuristics for the graph biseclion problem, Tech. Report, 86-8, RPI, 1986.
	GS1	Mark Goldberg , Thomas Spencer, A new parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.18 n.2, p.419-427, April 1989 [doi>10.1137/0218029]
	GS2	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]
	Jo	D. Johnson, Approximate Algorithms for Combinatorial Problems, j. of Computer and System Sciences 9, (1974), pp. 256-278.
	KR	R. M. Karp, V. Ramachandran, Handbook of Theoretical Computer Science, Preprint, University of California, Berkeley, (1987).
	KW	Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.266-272, December 1984 [doi>10.1145/800057.808690]
	LF	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]
	L1	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]
	L2	M. Luby, Removing Randomness in Parallel Computation Withou~ a Processor Penalty, in Proc. 29th Annual Symp. on Foundation of Computer Science, (1988), pp. 162-173.
	SV	Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
	TV	R. Tarjan, V. Vishkin An Efficient Parallel Biconnectivity Algorithm, SIAM J. Comp., 14, (1985), pp. 862-874.
	Tu	P. Tfiran, On the theory of graphs, Colloq. Math. 3 (1954), pp. 19-30.