Linear approximation of shortest superstrings

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear approximation of shortest superstrings

Full text

Pdf (959 KB)

Source

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

New Orleans, Louisiana, United States

Pages: 328 - 336

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Avrim Blum	Massachusetts Institute of Technology, Cambridge, MA
Tao Jiang	McMaster Univ., Hamilton, Ontario, CANADA
Ming Li	Univ. of Waterloo, Ontario, CANADA
John Tromp	CWI, Amsterdam, The Netherlands
Mihalis Yannakakis	AT&T Bell Labs. Murray Hill, NJ

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): 16, Citation Count: 6

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/103418.103455 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	J. Gallant, D. Maier, j. Storer. On finding minimal length superstring. Journal of Computer and System Sciences 20, 50-58, 1980.
	2	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
	3	A. Lesk, Computational molecular biology, Oxford University Press, Inc., New York, NY, 1988
	4	M. Li. Towards a DNA sequencing theory. 31st IEEE Symp. on Foundations of Computer Science, 125-134, 1990.
	5	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	6	Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62233]
	7	C. Pap#dimitriou and M Yannakaki#. The t#av#ling salesman problem with distances one and two. Mathematics of Opera#ions Research. To appear.
	8	H. Peltola, H. Soderlund, J. Tarhio, and E. Ukkonen. Algorithms for some string matching problems arising in molecular genetics. Information Processing 83 (Proc. IFIP Congress, 1983) 53-64.
	9	James A. Storer, Data compression: methods and theory, Computer Science Press, Inc., New York, NY, 1987
	10	J. Tarhio , E. Ukkonen, A greedy approximation algorithm for constructing shortest common superstrings, Theoretical Computer Science, v.57 n.1, p.131-145, April 1988 [doi>10.1016/0304-3975(88)90167-3]
	11	J. S. Turner, Approximation algorithms for the shortest common superstring problem, Information and Computation, v.83 n.1, p.1-20, Oct. 1989 [doi>10.1016/0890-5401(89)90044-8]
	12	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

CITED BY 6

	S. Rao Kosaraju , Arthur L. Delcher, Large-scale assembly of DNA strings and space-efficient construction of suffix trees, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.169-177, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Richard M. Karp, Mapping the genome: some combinatorial problems arising in molecular biology, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.278-285, May 16-18, 1993, San Diego, California, United States
	Mihalis Yannakakis, On the approximation of maximum satisfiability, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.1-9, September 1992, Orlando, Florida, United States
	Farid Alizadeh , Richard M. Karp , Lee A. Newberg , Deborah K. Weisser, Physical mapping of chromosomes: a combinatorial problem in molecular biology, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.371-381, January 25-27, 1993, Austin, Texas, United States
	Atsuko Yamaguchi , Koji Nakano , Satoru Miyano, An approximation algorithm for the minimum common supertree problem, Nordic Journal of Computing, v.4 n.3, p.303-316, Fall 1997
	Maxime Crochemore , Costas S. Iliopoulos , M. Sohel Rahman, Optimal prefix and suffix queries on texts, Information Processing Letters, v.108 n.5, p.320-325, November, 2008