[Back]

M. Horn, M. Djukanovic, C. Blum, G. Raidl:
"On the Use of Decision Diagrams for Finding Repetition-Free Longest Common Subsequences";
Talk: International Conference Optimization and Applications, Moscow, Russia; 2020-09-28 - 2020-10-02; in: "Optimization and Applications", LNCS / Springer, 12422 (2020), ISBN: 978-3-030-62866-6; 134 - 149.

We consider the repetition-free longest common subsequence(RFLCS) problem, where the goal is to find a longest sequence thatappears as subsequence in two input strings and in which each characterappears at most once. Our approach is to transform a RFLCS instanceto an instance of the maximum independent set (MIS) problem whichis subsequently solved by a mixed integer linear programming solver.To reduce the size of the underlying conflict graph of the MIS problem,a relaxed decision diagram is utilized. An experimental evaluation ontwo benchmark instance sets shows the advantages of the reduction ofthe conflict graphs in terms of shorter total computation times and thenumber of instances solved to proven optimality. A further advantage ofthe created relaxed decision diagrams is that heuristic solutions can beeffectively derived. For some instances that could not be solved to provenoptimality, new state-of-the-art results were obtained in this way.

http://dx.doi.org/10.1007/978-3-030-62867-3_11

https://publik.tuwien.ac.at/files/publik_293840.pdf