The Complexity of the Shortest Common Matching String Problem

Authors

Jonathan S. Turner, Washington University in St. LouisFollow

Document Type

Technical Report

Publication Date

1986-04-01

Filename

WUCS-86-9.pdf

Technical Report Number

WUCS-86-09

Abstract

This paper describes the shortest common matching string problem, which arises from a data analysis problem in molecular genetics, and shows that it is NP-complete.

Comments

Permanent URL: http://dx.doi.org/10.7936/K74B2ZMB

Recommended Citation

Turner, Jonathan S., "The Complexity of the Shortest Common Matching String Problem" Report Number: WUCS-86-09 (1986). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/844