Блог пользователя lllAlonsolll

Автор lllAlonsolll, история, 10 лет назад, По-английски

Hi everyone! Today I was looking for a way to solve de LCS (Longest Common Subsequence) problem for n strings and I found a curious comment of a member saying that this problem can be reduced to a Vertex Cover. Could someone please help me explaining how to do it?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

There is a paper here proving reduction to PSAT (Propositional SATisfiability problem)