NP-hards problem med minsta gemensamma strängpartition frågar om två strängar x och y var och en kan delas upp i de flesta k-delsträngar så att båda partitionerna använder exakt samma delsträngar i en annan ordning. Vi presenterar den första fasta parameteralgoritmen för minsta gemensamma strängpartition med hjälp av endast parameter k.
Nyligen, Bulteau och Komusiewicz REF har infört den första fasta-parameter algoritm för MCSP problem med hjälp av parameter k bara.
Minimum Common String Partition Parameterized by Partition Size is Fixed-Parameter Tractable
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}