067-2005

MO640 - Questão para a prova oral
Número: 067
Enunciado:
Com relação ao artigo de Kaplan, Shamir e Tarjan, entitulado "Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals", dada a seguinte permutação com sinais (3 1 6 5 -2 4), quais vértices do grafo de sobreposição (OV(π)) seriam orientados:

1. (0,1) e (6,7)
2. (2,3) e (4,5)
3. (6,7) e (12,13)
4. (8,9) e (10,11)
5. NDA

Autor(a): Marcelo de Almeida Oliveira