Advertisement
Guest User

Untitled

a guest
May 25th, 2019
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.58 KB | None | 0 0
  1. Camerini (`G=(V, E)`):
  2. - Se `|E| = |V| - 1`:
  3. - Devolva a maior aresta de `E`
  4. - Calcule a mediana aproximada usando `Median of medians`
  5. - Particione as arestas em `A` (menores ou iguais a mediana) e `B` (maiores que a mediana)
  6. - Seja `F` a floresta devolvida pelo `Kruskal` **sem ordenação** aplicado ao grafo `G' = (V, A)`
  7. - Se `F` tiver só uma árvore:
  8. - Devolva Camerini(`G' = (V, A)`)
  9. - Senão:
  10. - Seja `V'` o conjunto de vértices de `V` contraindo os que estão na mesma árvore em `F`, isto é, considerando cada árvore de `F` como uma só
  11. - Devolve Camerini(`G' = (V', B)`)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement