Minimum common string partition problem: hardness and approximations.

Goldstein, Avraham; Kolman, Petr; Zheng, Jie

Displaying similar documents to “Minimum common string partition problem: hardness and approximations.”

Reversal distance for strings with duplicates: linear time approximation using hitting set.

Kolman, Petr, Walen, Tomasz (2007)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Finding $H$ -partitions efficiently

Simone Dantas, Celina M. H. de Figueiredo, Sylvain Gravier, Sulamita Klein (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We study the concept of an $H$ -partition of the vertex set of a graph $G$ , which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph $H$ , with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties:...