On testing consecutive-ones property in parallel

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On testing consecutive-ones property in parallel

Full text

Pdf (1.07 MB)

Source

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

Santa Barbara, California, United States

Pages: 234 - 243

Year of Publication: 1995

ISBN:0-89791-717-0

Authors

F. S. Annexstein	Department of ECECS, University of Cincinnati, Cincinnati, OH
R. P. Swaminathan	Department of ECECS, University of Cincinnati, Cincinnati, OH

Sponsors

European Theoretical :
IEEE : Institute of Electrical and Electronics Engineers
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 13, Citation Count: 0

Additional Information:

references 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/215399.215449 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	Farid Alizadeh , Richard M. Karp , Deborah K. Weisser , Geoffrey Zweig, Physical mapping of chromosomes using unique probes, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.489-500, January 23-25, 1994, Arlington, Virginia, United States
	2	Robert E. Bixby , Donald K. Wagner, An almost linear-time algorithm for graph realization, Mathematics of Operations Research, v.13 n.1, p.99-123, February 1988 [doi>10.1287/moor.13.1.99]
	3	C. Berge (1972): Balanced Matrices. Mathematical Programming 2, pp. 19-31.
	4	John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
	5	K.S Booth and G.S. Luekcr (1976): Testing for consecutive l's property, interval graphs and graph planarity using PQ- tree algorithms. Journal of Computer and System Sciences 13, pp. 335-37'9.
	6	Lin Chen , Yaacov Yesha, Parallel recognition of the consecutive ones property with applications, Journal of Algorithms, v.12 n.3, p.375-392, Sept. 1991 [doi>10.1016/0196-6774(91)90010-V]
	7	W.H. Cunningham and J. Edmonds (1980): A combinatorial decomposition theory. Canadian Journal o} Mathematics 32, pp. 734-765.
	8	N. Dog, M.S. Krlslmamoorthy, and M.A. Lantpton (1987): Exact and approximate solutions for the gate matrix problem. IEEE Transactions on Computer-Aided Design 6, pp. 79-84.
	9	Donald Fussell , Vijaya Ramachandran , Ramakrishna Thurimella, Finding triconnected components by local replacement, SIAM Journal on Computing, v.22 n.3, p.587-616, June 1993 [doi>10.1137/0222040]
	10	Sakti P. Ghosh, Data base organization for data management (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1986
	11	J. Hopcroft and R.E. Tarjan (1973): Dividing a graph into triconnected components. SIAM Journal on Computing 2, pp. 135-I 58.
	12	Wen-Lian Hsu, A Simple Test for the Consecutive Ones Property, Proceedings of the Third International Symposium on Algorithms and Computation, p.459-468, December 16-18, 1992
	13	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]
	14	P.N. Klein (1988): Emcicnt parallel algorithms for planar, chordal, and interval graphs, MIT/LCS/TR-426 (Ph.D. the-
	15	G.L Miller and J. Rclf (1985): Parallel tree contraction and its application. In 26th Symp. on Found. of Comput, Science, pp. 478-489.
	16	R.P. Swam}nathan and D.K. Wagner (1994): On the consccutlvc-rctricvalproblem. SIAM Journal on Computing 23(3), pp. 1028-1046.
	17	R.E. Tarjan and U. Vishldn (1985): An efficient parallel biconnectivity algorithm. SIAM Journal on Computing 14(4), pp. 862-874.
	18	K. Truemper (1993): Matroid Decomposition. Academic Press, New York.
	19	A.C. Tucker. (1972): A structure theorem for the consecutive l's property. Journal of Combinatorial Theory (B) 12, pp. 153-162.
	20	W.T. Tutte (1966): Connectivity in graphs. University of Toronto Press, Toronto.
	21	H. Whitney (1932): Non-separable and planar graphs. Transactions o} American Mathematical Society 34, pp. 339-362.