Name
Abstract | ||
|---|---|---|
In this paper, we introduce the maximum duo-preservation string mapping problem (MPSM), which is complementary to the minimum common string partition problem (MCSP). When each letter occurs at most k times in any input string, the version of MPSM is called k-MPSM. In order to design approximation algorithms for MPSM, we also introduce the constrained maximum induced subgraph problem (CMIS) and the constrained minimum induced subgraph (CNIS) problem. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2014.02.017 | Theoretical Computer Science |
Keywords | DocType | Volume |
Approximation algorithm,Constrained maximum induced subgraph problem,Duo-preservation string mapping,Linear programming,Integer programming,Randomized rounding | Journal | 530 |
Issue | ISSN | Citations |
null | 0304-3975 | 12 |
PageRank | References | Authors |
0.63 | 7 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenbin Chen | 1 | 64 | 4.96 |
| Zhengzhang Chen | 2 | 198 | 25.62 |
| Nagiza F. Samatova | 3 | 861 | 74.04 |
| Lingxi Peng | 4 | 161 | 17.95 |
| Jianxiong Wang | 5 | 19 | 2.08 |
| Maobin Tang | 6 | 34 | 2.94 |