Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Camerini (`G=(V, E)`):
- - Se `|E| = |V| - 1`:
- - Devolva a maior aresta de `E`
- - Calcule a mediana aproximada usando `Median of medians`
- - Particione as arestas em `A` (menores ou iguais a mediana) e `B` (maiores que a mediana)
- - Seja `F` a floresta devolvida pelo `Kruskal` **sem ordenação** aplicado ao grafo `G' = (V, A)`
- - Se `F` tiver só uma árvore:
- - Devolva Camerini(`G' = (V, A)`)
- - Senão:
- - 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ó
- - Devolve Camerini(`G' = (V', B)`)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement