In this paper we consider the problem of covering a set of strings S with a set C of substrings in S, where C is said to cover S if every string in S can be written as a concatenation of the substrings in C. We discuss applications for the problem that arise in the context of computational biology and formal language theory. We then proceed to show that this problem is at least as hard as the PBMinimum Set Cover problem. In the main part of the paper, we focus on devising approximation algorithms for the problem using two generic paradigms – the local-ratio technique and linear programming rounding.

The Minimum Substring Cover Problem

RIZZI, ROMEO;
2007

Abstract

In this paper we consider the problem of covering a set of strings S with a set C of substrings in S, where C is said to cover S if every string in S can be written as a concatenation of the substrings in C. We discuss applications for the problem that arise in the context of computational biology and formal language theory. We then proceed to show that this problem is at least as hard as the PBMinimum Set Cover problem. In the main part of the paper, we focus on devising approximation algorithms for the problem using two generic paradigms – the local-ratio technique and linear programming rounding.
9783540779179
computational biology; formal language theory; approximation algorithms; local-ratio technique; linear programming rounding
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/409582
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact