( PDF ) Agoritmos para atualização de árvores geradoras mínimas em grafos dinâmicos

Download PDF

ads:

Universidade Federal Fluminense

RODRIGO FRANCO TOSO

NITER

2006

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

Universidade Federal Fluminense

RODRIGO FRANCO TOSO

Disserta¸c˜ao de Mestrado submetida ao Pro-

grama de P´os-Gradua¸c˜ao em Computa¸c˜ao da

Universidade Federal Fluminense como re-

quisito parcial para a obten¸c˜ao do t´ıtulo de

Mestre.

Area de concentra¸c˜ao: Otimiza¸c˜ao

Combinat´oria e Inteligˆencia Artiﬁcial.

Orientador:

Prof. Celso da Cruz Carneiro Ribeiro, Dr. Hab.

NITER

2006

ads:

Algoritmos para Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos

Dinˆamicos

Rodrigo Franco Toso

Disserta¸c˜ao de Mestrado submetida ao Pro-

grama de P´os-Gradua¸c˜ao em Computa¸c˜ao da

Universidade Federal Fluminense como re-

quisito parcial para a obten¸c˜ao do t´ıtulo de

Mestre.

Area de concentra¸c˜ao: Otimiza¸c˜ao

Combinat´oria e Inteligˆencia Artiﬁcial.

Aprovada por:

Prof. Celso da Cruz Carneiro Ribeiro, Dr. Hab. / IC-UFF

(Orientador)

Profa. Luciana Salete Buriol, D.Sc. / II-UFRGS

Dr. Maur´ıcio Guilherme de Carvalho Resende, Ph.D. /

AT&T Labs. Research

Profa. Maria Cristina Silva Boeres, Ph.D. / IC-UFF

Profa. Simone de Lima Martins, D.Sc. / IC-UFF

Niter´oi, 7 de Agosto de 2006.

“The purpose of science and technology is to develop useful information for humanity to

help people live their lives better. If we promise to withhold that information – if we keep

it secret – then we are betraying the mission of our ﬁeld. And this, I decided I shouldn’t

do.”

“O prop´osito da ciˆencia e tecnologia ´e prover conhecimentos ´uteis para a humanidade, de

forma a ajudar as pessoas a viver melhor. Se prometemos reter essa informa¸c˜ao – se a

mantemos em segredo – ent˜ao estamos traindo a miss˜ao da nossa ´area. E isso, eu decidi

que n˜ao devo fazer.”

Richard Stallman.

Aos meus pais, Ana Maria e Rubens, que dedicaram suas vidas para me dar

oportunidades as quais nunca tiveram. Nada disso seria poss´ıvel sem o amor e a

dedica¸c˜ao de vocˆes.

Antes de mais nada, minha vida s´o ´e assim, especial como a considero, por que dela

fazem parte pessoas especiais e ´unicas: meus amigos e familiares. Agrade¸co ent˜ao aos

amigos da Universidade Federal de Lavras (UFLA), da Universidade Federal Fluminense

(UFF) e das fam´ılias Franco e Toso. Em primeiro lugar, al´em de toda a turma 2000/2 da

UFLA, ﬁca um abra¸co aos membros do quarteto dinˆamico, Andr´e Fialho, Carlos Eduardo

(Sidnelson), Fabr´ıcio e Fl´avio. Seguindo a ordem, nunca poderia imaginar que encontraria

na UFF um lugar t˜ao caloroso para trabalhar e, claro, aprontar! Um agradecimento

especial aos amigos Alet´eia, Aline e Alexandre, Ary, Celso Ribeiro, Cristiane (Criix),

Cristina e Vinod, Daniela (Dani), Diego, Haroldo, Idalmis (Ida, minha melhor amiga

cubana), Jacques (Rat˜ao), Johnny, Kennedy, Luciana (Brugiolo e Pessˆoa), Luciana e

Robson, Luciano, Luis, Rafael (Guto e Sat˜a), Renatha (Rena) e Marcel, Renato, Tiago

(Facada e MacJovem), Stˆenio S˜a, Viviane (Vivs) e Jonivan, Warley (Toca)... E ﬁnalmente,

aos meus familiares: Ana Maria, Rubens e Ana Silvia (Byll) (pais e irm˜a); Zenith e

Jos´e (av´os); Zen´olia (tia-av´o). Tenho tantos tios e primos que daria uma p´agina... Um

agradecimento especial `as tias e tios Vera (tanto a Franco quanto a Toso), M´arcia e Eurico,

e Edson, pelo carinho e amor! Com certeza n˜ao coloquei aqui o nome de todos os que

merecem, mas minha mem´oria (eu diria RAM) no ﬁnal dessa disserta¸c˜ao j´a n˜ao ´e mais a

mesma...

Gostaria de agradecer aqueles que estiveram diretamente ligados a esse projeto, ou

seja, a todos professores do Instituto de Computa¸c˜ao da Universidade Federal Fluminense.

Tiveram participa¸c˜ao fundamental nesse trabalho os professores Celso (projeto e an´alise

de algoritmos), Christiano (teoria da computa¸c˜ao), Cristina (estruturas de dados) e Satoru

(paraleliza¸c˜ao de metaheur´ısticas, t´ecnicas de inteligˆencia computacional e otimiza¸c˜ao em

redes). Merece destaque o professor Vinod pelo exemplo de ´etica e dedica¸c˜ao `a UFF. Tem

tamb´em os professores da UFLA que ﬁzeram com que minha vida tomasse o rumo acadˆe-

mico, em especial: Renata (projeto e an´alise de algoritmos) e Ricardo (desenvolvimento

para sistemas m´oveis, otimiza¸c˜ao, redes de computadores, sistemas operacionais e, p or

Agradecimentos v

ﬁm (ufa!), orientador de projeto de conclus˜ao de curso).

Os lugares onde morei durante essa jornada tamb´em precisam de cita¸c˜ao especial. Pri-

meiro aos parceiros da Rep´ublica Buf´aria (que depois virou A Marvada), em Lavras/MG:

Fabr´ıcio, Fl´avio, Marcelo (Harry e Magal) e Renato (Quat´ı). Depois a R´ep Our (Nite-

r´oi/RJ), com alta rotatividade e, portanto, em ordem cronol´ogica: Fialho, Luis (Pa¸coc˜ao

e Suri), Rafael (B´atima), Emmanuel, Carlos Eduardo (Dudu), Rafael (Guto), Diego e

Warley (Toca).

Ao CNPq pela bolsa que custeou em torno de 40% do meu mestrado.

Aos membros da banca examinadora pelos coment´arios e sugest˜oes: Celso Ribeiro,

Cristina Boeres, Luciana Buriol, Maur´ıcio Resende e Simone Martins.

Agrade¸co aos funcion´arios da UFF que fazem toda a base (muitas vezes chata e

burocr´atica).

Angela, Izab ela, Jo˜ao e Maria, obrigado por todos os galhos quebrados (e

eu sei que n˜ao foram poucos – daria para desmatar uma ﬂoresta).

Sem d´uvida esse trabalho n˜ao teria uma bibliograﬁa impec´avel, texto bem escrito, foco

bem deﬁnido e consistˆencia (tudo bem, deixei a mod´estia de lado) se n˜ao fosse por conta

de um orientador que, embora geograﬁcamente distante, esteve sempre “interneticamente”

perto (sem contar os v´arios s´abados e domingos de reuni˜ao). Um agradecimento mais que

especial ao amigo, professor e orientador Celso.

O que ´a vida sem amor? Eu respondo que a vida simplesmente n˜ao teria sentido

sem amor de pai, de m˜ae, de irm˜ao e de amigo. Mas, al´em disso, a vida n˜ao teria

gra¸ca alguma se n˜ao existisse o amor de beijos na boca, abra¸cos apertados, conﬁdˆencias,

cumplicidade e tudo mais... A vida n˜ao teria gra¸ca alguma se eu n˜ao tivesse encontrado

a minha pequenininha Daniela. Sempre ao olhar ao c´eu existe uma estrela que chama

mais aten¸c˜ao que as outras – as vezes por seu brilho, as vezes por sua magia ou as vezes

sem qualquer explica¸c˜ao – e acho que vocˆe ´e essa estrela: repleta de magia, alegria, amor,

sorrisos, companheirismo, e de um quˆe a mais que ´e indescrit´ıvel! Love you...

O Problema das

Arvores Geradoras M´ınimas Dinˆamicas (PAGMD) tem como objetivo a

manuten¸c˜ao de uma ´arvore geradora m´ınima de um grafo sujeito a constantes mudan¸cas

estruturais, onde tais mudan¸cas podem ser inser¸c˜oes ou remo¸c˜oes de v´ertices, inser¸c˜oes

ou remo¸c˜oes de arestas e modiﬁca¸c˜oes em custos de arestas. Este problema ´e dito total-

mente dinˆamico quando ambas as opera¸c˜oes de inser¸c˜ao e remo¸c˜ao (ou de incremento e

decremento em custos de arestas) s˜ao permitidas. Por outro lado, este problema ´e dito

parcialmente dinˆamico ou semi-dinˆamico quando apenas um tipo de opera¸c˜ao ´e permitido

(inser¸c˜oes ou remo¸c˜oes, incrementos ou decrementos). Ainda, o problema ´e dito on-line

quando as altera¸c˜oes dinˆamicas s˜ao processadas em tempo real, ou seja, sem qualquer

tipo de pr´e-processamento.

O estudo de algoritmos para grafos dinˆamicos, em particular aqueles para a manuten-

¸c˜ao da ´arvore geradora m´ınima de um grafo em constante atualiza¸c˜ao, ´e motivado tanto

por raz˜oes te´oricas quanto por raz˜oes pr´aticas. Algoritmos e estruturas de dados dinˆami-

cas podem ser utilizados em uma vasta cole¸c˜ao de problemas cotidianos, a citar problemas

de otimiza¸c˜ao em redes (redes de computadores, telefonia e TV a cabo), metaheur´ısticas

e heur´ısticas de busca lo cal.

Neste trabalho ´e realizada uma avalia¸c˜ao experimental dos algoritmos para atuali-

za¸c˜ao da ´arvore geradora m´ınima de um grafo sujeito a altera¸c˜oes dinˆamicas nos custos

de suas arestas. Tais algoritmos podem ser ´uteis na implementa¸c˜ao de metaheur´ısticas

e heur´ısticas de busca local para problemas de projeto e otimiza¸c˜ao de redes de comu-

nica¸c˜ao, de maneira similar aos algoritmos envolvendo os problemas de caminho m´ınimo

estudados por Buriol et al. [6, 7, 8, 9] no contexto do problema de atribui¸c˜ao de custos

para o roteamento de pacotes em redes OSPF/IS-IS. Complementarmente, s˜ao propostos

um algoritmo e uma estrutura de dados especiﬁcamente desenvolvidos para o caso de

atualiza¸c˜ao em custos de arestas. O algoritmo proposto ´e de simples implementa¸c˜ao com-

putacional, podendo ser utilizado com qualquer estrutura de dados para representa¸c˜ao de

´arvores dinˆamicas.

Palavras-chave:

Arvore geradora m´ınima, ´arvore geradora de custo m´ınimo, grafos di-

nˆamicos, an´alise experimental de algoritmos, complexidade computacional.

The Dynamic Minimum Spanning Tree Problem (DMSTP) is that of maintaining a mi-

nimum spanning tree (MST) of a dynamically changing graph, where these changes (or

operations) can be insertions and deletions of vertices, insertions or deletions of edges,

and modiﬁcations of edge weights. The problem is said to be fully dynamic if both inser-

tion and deletion operations are allowed (or if the edge weights can increase or decrease).

Otherwise, the problem is said to be partially dynamic or semi dynamic if only one kind

of operation is allowed (either edge deletions or insertions, either weight increases or de-

creases). Also, the problem is said to be on-line if the dynamic changes must be processed

in real time (i.e. there is no preprocessing and updates are performed one by one).

The study of dynamic graph algorithms, in particular those for maintaining a mini-

mum spanning tree of a dynamically changing graph, is motivated by both practical and

theoretical reasons. Dynamic algorithms and data structures can be used in a wide range

of real-life problems, e.g. in network-related problems (computer, telephony and cable-TV

networks), metaheuristics and local search heuristics.

In this work, we make a step toward the experimental evaluation of algorithms to

update a minimum spanning tree after edge weight changes. Such algorithms are particu-

larly helpful in the implementation of metaheuristics and local search heuristics for solving

broadcast optimization and design problems in communication networks, similar to the

algorithms involving dynamic shortest path problems studied by Buriol et al. [6, 7, 8, 9]

in the context of the weight setting problem in OSPF/IS-IS routing. Complementary, we

propose and evaluate both a new algorithm and a new data structure speciﬁcally designed

for the edge weight updating variant of the DMSTP. The new algorithm is quite simple

to implement and can be used with any data structure for dynamic trees representation.

Keywords:. Minimum spanning trees, minimum weight spanning trees, dynamic graphs,

experimenal analysis of algorithms, computational complexity.

AGM :

Arvore Geradora M´ınima (p´agina 1)

FGM : Floresta Geradora M´ınima (p´agina 34)

PCM : Problema do Caminho M´ınimo (p´agina 1)

RD-trees :

Arvores dinˆamicas reversas (p´agina 26)

DRD-trees :

Arvores dinˆamicas duplamente encadeadas (p´agina 52)

ST-trees :

Arvores de Sleator e Tarjan [41] (p´agina 26)

ET-trees :

Arvores de ciclos eulerianos [26] (p´agina 26)

2.1 Formula¸c˜ao e Aplica¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2.1 Algoritmo de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2.2 Algoritmo de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3 Resumo do Cap´ıtulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.1

Arvores Dinˆamicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.1.1 An´alise das Implementa¸c˜oes de

Arvores Dinˆamicas . . . . . . . . . 13

3.1.2 RD-trees:

Arvores Dinˆamicas Reversas . . . . . . . . . . . . . . . . 14

3.1.3 ST-trees:

Arvores Dinˆamicas de Sleator e Tarjan . . . . . . . . . . 17

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Comple-

xidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2.1 Conceitos B´asicos sobre Algoritmos Dinˆamicos . . . . . . . . . . . . 19

3.2.2 Algoritmos para Inser¸c˜ao e Remo¸c˜ao de V´ertices . . . . . . . . . . . 22

3.2.3 Algoritmos e Estruturas de Dados para Inser¸c˜ao e Remo¸c˜ao de Arestas 23

3.2.3.1

Arvores Topol´ogicas para Inser¸c˜oes e Remo¸c˜oes de Arestas 23

Sum´ario x

3.2.3.2 T´ecnica de Esparsiﬁca¸c˜ao . . . . . . . . . . . . . . . . . . 26

3.2.3.3 Algoritmo HK . . . . . . . . . . . . . . . . . . . . . . . . 27

3.2.3.4 Algoritmo HDT . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2.4 Algoritmos para Altera¸c˜ao no Custo de Arestas . . . . . . . . . . . 31

3.3 An´alises Experimentais em AGMs Dinˆamicas . . . . . . . . . . . . . . . . . 33

3.4 An´alise dos Algoritmos para Atualiza¸c˜ao de

Arvores Geradoras M´ınimas . 36

3.5 Resumo do Cap´ıtulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.1 DRD-trees: Uma Proposta de

Arvores Dinˆamicas . . . . . . . . . . . . . . 39

4.2 Consultas de Conectividade em Tempo Constante . . . . . . . . . . . . . . 41

4.3 Resumo do Cap´ıtulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.1 Estrutura de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.2 Algoritmo para Decremento no Custo de Arestas . . . . . . . . . . . . . . . 45

5.3 Algoritmo para Incremento no Custo de Arestas . . . . . . . . . . . . . . . 46

5.4 Resumo do Cap´ıtulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6.1 Estruturas de Dados:

Arvores Dinˆamicas . . . . . . . . . . . . . . . . . . . 51

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 56

6.2.1 Experimentos com Instˆancias Sint´eticas . . . . . . . . . . . . . . . . 58

6.2.1.1 Atualiza¸c˜oes Aleat´orias em Grafos Aleat´orios . . . . . . . 58

6.2.1.2 Atualiza¸c˜oes Estruturadas em Grafos Aleat´orios . . . . . . 61

6.2.1.3 Experimento Complementar: Variando o N´umero de V´er-

tices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

6.2.1.4 Atualiza¸c˜oes Aleat´orias em Grafos k-Clique . . . . . . . . 65

Sum´ario xi

6.2.1.5 Atualiza¸c˜oes Estruturadas em Grafos k-Clique . . . . . . . 65

6.2.1.6 Considera¸c˜oes sobre os Experimentos com Instˆancias Sin-

t´eticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.2.2 Experimentos com Instˆancias da Literatura . . . . . . . . . . . . . . 68

6.2.2.1 Atualiza¸c˜oes Aleat´orias . . . . . . . . . . . . . . . . . . . 69

6.2.2.2 Atualiza¸c˜oes Estruturadas . . . . . . . . . . . . . . . . . . 72

6.2.2.3 Comparando Algoritmos Dinˆamicos com Algoritmos Es-

t´aticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6.2.2.4 Atualiza¸c˜oes Incrementais em Arestas da AGM . . . . . . 77

6.2.2.5 Considera¸c˜oes sobre os Experimentos com Instˆancias Reais 77

6.3 Resumo do Cap´ıtulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

2.1 Execu¸c˜ao do algoritmo de Kruskal. . . . . . . . . . . . . . . . . . . . . . . 6

2.2 Execu¸c˜ao do algoritmo de Prim. . . . . . . . . . . . . . . . . . . . . . . . . 8

3.1 Uma AGM mapeada por uma ´arvore reversa. . . . . . . . . . . . . . . . . . 15

3.2 Opera¸c˜oes em uma estrutura de dados RD-trees T = (V, E



). . . . . . . . . 17

3.3 Um exemplo de AGM e seu particionamento em caminhos. . . . . . . . . . 18

3.4 Grafo G = (V, E) e sua AGM T = (V, E



). . . . . . . . . . . . . . . . . . . 19

3.5 AGMs resultantes de inser¸c˜oes e remo¸c˜oes de v´ertices em G. . . . . . . . . 20

3.6 AGMs resultantes de inser¸c˜oes e remo¸c˜oes de arestas em G. . . . . . . . . . 20

3.7 AGMs resultantes de mudan¸cas no custo de arestas. . . . . . . . . . . . . . 21

3.8 Execu¸c˜ao do algoritmo de Spira e Pan [44] para a inser¸c˜ao do v´ertice h. . . 24

3.9 Um grafo e sua respectiva ´arvore topol´ogica. . . . . . . . . . . . . . . . . . 25

3.10

Arvore de esparsiﬁca¸c˜ao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.1 AGM representada atrav´es de DRD-trees. . . . . . . . . . . . . . . . . . . . 40

6.1 Tempos de CPU para a execu¸c˜ao de 100000 consultas de conectividade em

´arvores aleat´orias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

6.2 Tempos de CPU para a execu¸c˜ao de 100000 consultas de conectividade em

´arvores lineares. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

6.3 Tempos de CPU para a execu¸c˜ao de 100000 consultas de conectividade em

´arvores balanceadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

6.4 Tempos de CPU para a execu¸c˜ao de 100000 consultas de conectividade em

´arvores aleat´orias sujeitas altera¸c˜oes estruturais. . . . . . . . . . . . . . . . 56

6.5 Tempos de CPU para a execu¸c˜ao de 100000 opera¸c˜oes mistas de link e cut. 57

Lista de Figuras xiii

6.6 Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes aleat´orias de custos

em grafos aleat´orios contendo 1000 v´ertices. . . . . . . . . . . . . . . . . . 59

6.7 Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes aleat´orias de custos

em grafos aleat´orios contendo 2000 v´ertices. . . . . . . . . . . . . . . . . . 60

6.8 Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes aleat´orias de custos

em grafos aleat´orios contendo 4000 v´ertices. . . . . . . . . . . . . . . . . . 61

6.9 Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes estruturadas de

custos em grafos aleat´orios contendo 1000 v´ertices. . . . . . . . . . . . . . 62

6.10 Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes estruturadas de

custos em grafos aleat´orios contendo 2000 v´ertices. . . . . . . . . . . . . . 63

6.11 Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes estruturadas de

custos em grafos aleat´orios contendo 4000 v´ertices. . . . . . . . . . . . . . 63

6.12 Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes aleat´orias de custos

em grafos aleat´orios contendo 99000 arestas. . . . . . . . . . . . . . . . . . 64

6.13 Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes aleat´orias de custos

em grafos k-Clique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

6.14 Tempos de CPU para a execu¸c˜ao de 20000 opera¸c˜oes de incremento em

arestas inter-clique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.1 Evolu¸c˜ao dos algoritmos para grafos dinˆamicos . . . . . . . . . . . . . . . . 32

3.2 Algoritmos implementados por Amato et al. [4]. . . . . . . . . . . . . . . . 34

6.1 Estruturas de dados analisadas experimentalmente. . . . . . . . . . . . . . 52

6.2 Experimentos sobre estruturas de dados para ´arvores dinˆamicas. . . . . . . 52

6.3 Algoritmos analisados experimentalmente. . . . . . . . . . . . . . . . . . . 57

6.4 Experimentos sint´eticos realizados. . . . . . . . . . . . . . . . . . . . . . . 58

6.5 Tempos de CPU (segundos) para as instˆancias Random4-n ap´os 20000 atu-

aliza¸c˜oes aleat´orias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

6.6 Tempos de CPU (segundos) para as instˆancias Long-n ap´os 20000 atuali-

za¸c˜oes aleat´orias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

6.7 Tempos de CPU (segundos) para as instˆancias Square-n ap´os 20000 atua-

liza¸c˜oes aleat´orias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.8 Tempos de CPU (segundos) para as instˆancias USA-road-d ap´os 20000

atualiza¸c˜oes aleat´orias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.9 Tempos de CPU (segundos) para as instˆancias Random4-n ap´os 20000 atu-

aliza¸c˜oes estruturadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.10 Tempos de CPU (segundos) para as instˆancias Long-n ap´os 20000 atuali-

za¸c˜oes estruturadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.11 Tempos de CPU (segundos) para as instˆancias Square-n ap´os 20000 atua-

liza¸c˜oes estruturadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

6.12 Tempos de CPU (segundos) para as instˆancias USA-road-d ap´os 20000

atualiza¸c˜oes estruturadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

6.13 Quantidade de atualiza¸c˜oes processadas pelos algoritmos cl´assicos para

AGMs utilizando mesmo tempo de CPU gasto pelo Algoritmo RT(DRD+ST). 76

Lista de Tabelas xv

6.14 Tempos de CPU (segundos) para as instˆancias Random4-n ap´os 20000 in-

crementos de valor n/16 em arestas da AGM. . . . . . . . . . . . . . . . . 78

6.15 Tempos de CPU (segundos) para as instˆancias Long-n ap´os 20000 incre-

mentos de valor n/16 em arestas da AGM. . . . . . . . . . . . . . . . . . . 78

6.16 Tempos de CPU (segundos) para as instˆancias Square-n ap´os 20000 incre-

mentos de valor n/16 em arestas da AGM. . . . . . . . . . . . . . . . . . . 79

Os problemas de otimiza¸c˜ao em redes s˜ao de grande interesse te´orico e pr´atico para a

ciˆencia da computa¸c˜ao. O interesse em sua teoria, onde destacam-se as pesquisas por

algoritmos e implementa¸c˜oes eﬁcientes, ´e complementado por suas in´umeras aplica¸c˜oes

em situa¸c˜oes cotidianas. Exemplos de problemas de otimiza¸c˜ao em redes incluem os

problemas de caminho m´ınimo (PCM), ´arvore geradora m´ınima (AGM) e ﬂuxo m´aximo.

Ainda que sejam de grande valia do ponto de vista pr´atico, os algoritmos cl´assicos

desenvolvidos para os problemas de otimiza¸c˜ao em redes n˜ao prevˆeem qualquer forma

de altera¸c˜ao na rede propriamente dita. Entretanto, redes reais podem estar sujeitas a

altera¸c˜oes freq

uentes – inser¸c˜oes ou remo¸c˜oes de n´os; inser¸c˜oes ou remo¸c˜oes de arestas; ou

mudan¸cas no custo de arestas – trazendo consigo a necessidade de atualiza¸c˜ao da solu¸c˜ao

anteriormente gerada. Uma rede ´e facilmente representada atrav´es de um grafo, uma es-

trutura de dados onde os algoritmos e implementa¸c˜oes computacionais s˜ao extremamente

eﬁcientes. As caracter´ısticas dinˆamicas das redes fazem com que os algoritmos cl´assicos

sejam, muitas vezes, obrigados a descartar totalmente a solu¸c˜ao anterior para, ent˜ao, re-

construir a nova solu¸c˜ao a partir do grafo atualizado. Embora esses algoritmos tenham

complexidade polinomial, recalcular uma propriedade de um grafo, al´em de computacio-

nalmente caro, pode ser ineﬁciente por n˜ao aproveitar a solu¸c˜ao gerada no passo anterior

`a altera¸c˜ao.

Assim, visando evitar o problema de, ap´os cada atualiza¸c˜ao da rede, ignorar toda

a solu¸c˜ao existente e partir para a constru¸c˜ao de uma nova solu¸c˜ao, foram propostos

algoritmos dinˆamicos para os mais importantes problemas de otimiza¸c˜ao em redes. Dado

um grafo representando a rede em quest˜ao, a solu¸c˜ao para um problema sobre esse grafo e

a altera¸c˜ao que ocorreu na estrutura do mesmo, esses algoritmos s˜ao capazes de atualizar

a solu¸c˜ao obsoleta, tornando-a v´alida para o grafo resultante da modiﬁca¸c˜ao estrutural.

1 Introdu¸c˜ao 2

A ´area de algoritmos para grafos dinˆamicos avan¸cou muito desde seu in´ıcio. A partir

de ent˜ao, foram propostos algoritmos e estruturas de dados eﬁcientes para os principais

problemas de otimiza¸c˜ao em redes.

Al´em de aplica¸c˜oes em problemas reais, os algoritmos dinˆamicos podem ser aplicados

em sub-problemas de programa¸c˜ao inteira e em m´etodos de busca local de heur´ısticas

e metaheur´ısticas. Acredita-se que essas aplica¸c˜oes sejam de extrema importˆancia para

a ´area de otimiza¸c˜ao combinat´oria, e trazem consigo um requisito adicional para esses

algoritmos: al´em da eﬁciˆencia, a simplicidade para implementa¸c˜ao computacional ´e fun-

damental. Nesse caminho, foram propostos trabalhos envolvendo algoritmos dinˆamicos

para o problema de caminho m´ınimo em grafos, com aplica¸c˜oes em m´etodos de busca

local de heur´ısticas e metaheur´ısticas [6, 7, 8, 9].

Este trabalho tˆem seu foco em algoritmos e estruturas de dados dinˆamicas para o

problema da ´arvore geradora m´ınima, considerando o fato de n˜ao haver na literatura um

trabalho como os apresentados em [6, 7, 8, 9] para o problema de caminho m´ınimo em

grafos dinˆamicos, bem como sua importˆancia para a ´area de otimiza¸c˜ao.

Arvores geradoras

m´ınimas tˆem aplica¸c˜oes em problemas como os de transmiss˜ao e de conectividade em redes

e, at´e mesmo, em problemas de biologia computacional. A variante dinˆamica estudada

foi a de altera¸c˜oes – incrementos e decrementos – nos custos das arestas.

Nesta disserta¸c˜ao, apresenta-se uma nova estrutura de dados simples e eﬁciente para

o problema das ´arvores dinˆamicas. Prop˜oe-se e avalia-se experimentalmente um algoritmo

extremamente simples, mas ainda assim eﬁciente, para a atualiza¸c˜ao da ´arvore geradora

m´ınima de um grafo sujeito a altera¸c˜oes nos custos das arestas. O trabalho est´a organizado

em sete cap´ıtulos. O conte´udo de cada cap´ıtulo ´e apresentado a seguir.

• Cap´ıtulo 1: apresenta este trabalho sob uma ´otica geral e abrangente, situando seu

contexto e delineando o escopo a ser desenvolvido.

• Cap´ıtulo 2: introduz o problema da ´arvore geradora de custo m´ınimo, trazendo

algoritmos e estruturas de dados para a vers˜ao est´atica desse problema.

• Cap´ıtulo 3: apresenta o estado da arte para algoritmos e estruturas de dados dinˆa-

micas para ´arvores geradoras m´ınimas.

• Cap´ıtulo 4: prop˜oe e analisa uma estrutura de dados para a representa¸c˜ao de ´arvores

dinˆamicas.

1 Introdu¸c˜ao 3

• Cap´ıtulo 5: prop˜oe e discute um algoritmo para atualiza¸c˜ao da ´arvore geradora

m´ınima de um grafo dinˆamico.

• Cap´ıtulo 6: conduz uma an´alise experimental comparando o algoritmo e a estrutura

de dados propostos com alguns dos mais importantes algoritmos da literatura.

• Cap´ıtulo 7: traz as conclus˜oes e trabalhos futuros a esta disserta¸c˜ao.

Neste cap´ıtulo ´e introduzido o problema cl´assico da ´arvore geradora m´ınima (AGM),

incluindo sua formula¸c˜ao matem´atica, aplica¸c˜oes, algoritmos e complexidades.

Em problemas de conex˜ao em redes, onde n pontos (n´os) devem ser conectados atrav´es de

n−1 arestas, geralmente existe o requisito de se obter o conjunto de arestas que minimize

um certo custo a ser gasto. Um exemplo que ilustra esta aﬁrma¸c˜ao ´e o problema de se

conectar todos os n computadores de uma rede de forma a minimizar os gastos com ﬁbras

´oticas. Nestes problemas, deseja-se encontrar uma ´arvore de custo m´ınimo que conecte

todos os n´os da rede.

Formalmente, dada uma rede modelada como um grafo G = (V, E), onde V ´e um

conjunto de n n´os e E ´e um conjunto de m arestas que conectam dois n´os de V , e uma

fun¸c˜ao w : E → R que especiﬁca o custo da aresta (u, v) ∈ E, o problema da AGM

consiste em encontrar a ´arvore T = (V, E



) com E



⊆ E que minimiza a fun¸c˜ao objetivo

w(T ) =



(u,v)∈E



w(u, v). (2.1)

Arvores geradoras m´ınimas s˜ao comumente utilizadas em problemas como: broadcast

em redes de computadores, planejamento e concep¸c˜ao de redes de transmiss˜ao (telefonia,

energia el´etrica e TV a cabo, p or exemplo), rotas m´ınimas para a cob ertura de cidades,

gera¸c˜ao de solu¸c˜oes heur´ısticas para problemas como os do caixeiro viajante [23, 24] e

2.2 Algoritmos 5

problemas de biologia computacional, entre outros.

Na literatura, existem v´arias maneiras de se determinar a ´arvore geradora m´ınima de

um grafo, todas elas baseadas em algoritmos gulosos. Estes constituem uma t´ecnica de

projeto de algoritmos onde, a cada passo ou itera¸c˜ao, uma decis˜ao ´e tomada com base

na melhor das op¸c˜oes existentes no momento. Este trabalho apresenta os dois algoritmos

mais conhecidos: o algoritmo de Kruskal [33], na Se¸c˜ao 2.2.1, e o algoritmo de Prim [37],

na Se¸c˜ao 2.2.2.

Este algoritmo foi proposto em 1956 por Kruskal [33]. Seu princ´ıpio de funcionamento ´e

baseado na ordena¸c˜ao de todas as arestas do conjunto E. Constr´oi-se a ´arvore geradora

m´ınima T = ( V, E



), onde E



´e inicialmente um conjunto vazio. Analisa-se cada aresta

(u, v) ∈ E em ordem crescente de custo. De acordo com essa ordem, se os n´os u ∈ V e

v ∈ V pertencem a componentes conexas distintas da arborescˆencia corrente T = (V, E



ent˜ao a aresta (u, v) ´e adicionada a E



e, conseq

uentemente, as componentes conexas

onde se encontram os v´ertices u e v s˜ao unidas em uma ´unica componente. Ap´os serem

inseridas n − 1 arestas, E



cont´em as arestas necess´arias para conectar todos os n´os de V

com custo m´ınimo. A Figura 2.1 ilustra a execu¸c˜ao do algoritmo de Kruskal em um grafo

dado.

Na Figura 2.1, a ´arvore geradora m´ınima T ´e representada pelas arestas mais escuras.

Seguindo a ordem crescente de custo, a aresta (b, f) ´e analisada e inclu´ıda no conjunto



, j´a que os n´os b e f n˜ao fazem parte da mesma componente conexa (a). Da mesma

forma, em (b) ´e inserida a aresta (c, e), seguida pelas inser¸c˜oes das arestas (f, g), (a, b) e

(d, f). J´a a aresta (a, d) n˜ao deve ser inclu´ıda em T , visto que a inclus˜ao desta resultaria

em um ciclo em T , descaracterizando a propriedade de que uma ´arvore n˜ao deve possuir

ciclos (f). A aresta (b, c) ´e ent˜ao inserida em T , j´a que as mesmas se encontram em

componentes distintas (g). Por ﬁm, em (h) e (i), as arestas (e, f) e (e, g), respectivamente,

s˜ao descartadas por tamb´em causarem ciclos em T .

E importante salientar que os passos

(h) e (i) poderiam ser omitidos pelo algoritmo, visto que n−1 arestas j´a foram selecionadas

para compor a ´arvore geradora m´ınima T .

O Algoritmo 1 formaliza os passos acima citados, com corretude demonstrada em [12].

2.2 Algoritmos 6

(a) (b) (c)

(d) (e) (f)

(g) (h) (i)

Figura 2.1: Execu¸c˜ao do algoritmo de Kruskal.

Sua implementa¸c˜ao requer uma estrutura de dados que mantenha atualizados os conjun-

tos disjuntos que formam as componentes conexas da arborescˆencia corrente T . Suas

opera¸c˜oes s˜ao apresentadas abaixo:

• MakeSet(u): cria um v´ertice u, pertencente ao conjunto disjunto contendo apenas

• Union(u, v): une os conjuntos disjuntos contendo u e v atrav´es da aresta (u, v).

• Find(u): retorna o conjunto disjunto ao qual u pertence.

A complexidade do algoritmo de Kruskal depende da maneira como a estrutura de

dados para manuten¸c˜ao de componentes conexas ´e implementada. Se a estrutura set-

union [46] ´e utilizada, ent˜ao a execu¸c˜ao de m ≥ n opera¸c˜oes Find e n−1 opera¸c˜oes Union

2.2 Algoritmos 7

Algoritmo 1 M´etodo de Kruskal

Entrada: Grafo G = (V, E) e custos w.

1: Ordenar E em ordem crescente de custos;

2: E



← ∅;

3: para todo v ∈ V fa¸ca

4: MakeSet(v);

5: ﬁm para

6: para todo (u, v) ∈ E em ordem crescente de custos fa¸ca

7: se Find(u) = Find(v) ent˜ao

8: E



← E



∪ {(u, v)};

9: Union(u, v);

10: ﬁm se

11: ﬁm para

possui complexidade de O(mα(m, n)). Se as n opera¸c˜oes MakeSet realizadas na linha 2

s˜ao levadas em considera¸c˜ao, a complexidade relacionada `a estrutura de dados set-union

´e O((m + n) · α(m, n)). Como α(m, n) ´e uma fun¸c˜ao que cresce muito lentamente, cal-

culada a partir do inverso da fun¸c˜ao de Ackermann [46], a complexidade do algoritmo

passa a depender do tempo em que a ordena¸c˜ao das arestas pode ser realizada, ou seja,

O(m log m). Dado ainda que m < n

, ent˜ao log m = O(log n), o que resulta na complexi-

dade de O(m log n). Um estudo completo sobre estruturas de dados para armazenamento

e atualiza¸c˜ao de componentes conexas ´e apresentado por Galil e Italiano [20].

O algoritmo de Prim [37] tamb´em ´e um m´etodo guloso. Por´em, usa apenas uma ´arvore

(componente conexa), inicialmente vazia. A AGM ´e ent˜ao constru´ıda da seguinte maneira:

inicia-se uma estrutura de dados denominada ﬁla de prioridades (heap) contendo todos

os n´os de V , que inicialmente ter˜ao prioridade p = ∞. Partindo de um n´o raiz r escolhido

arbitrariamente, as prioridades dos n´os conectados `a raiz s˜ao atualizadas de acordo com

o custo entre r e o n´o v analisado. Deste modo, aquele v´ertice v com a maior prioridade

(ou seja, o menor custo para conex˜ao `a AGM) ´e adicionado a T , e as prioridades dos n´os

conectados a v tamb´em s˜ao atualizadas na ﬁla de prioridades. Este passo guloso se repete

at´e que todos os n´os sejam retirados dessa ﬁla, quando a AGM T conectar´a todos os n´os

v ∈ V . A Figura 2.2 ilustra uma execu¸c˜ao t´ıpica do algoritmo de Prim.

Na Figura 2.2, o primeiro passo ´e selecionar o n´o raiz a e atualizar seu custo para 0,

fazendo com que este seja o primeiro n´o a ser removido da ﬁla de prioridades e tamb´em

alterando os custos de acesso aos n´os b e d para 3 e 5, respectivamente (a). O pr´oximo

2.2 Algoritmos 8

(a) (b) (c)

(d) (e) (f)

(g)

Figura 2.2: Execu¸c˜ao do algoritmo de Prim.

passo ´e remover o n´o b da ﬁla de prioridades e atualizar as estimativas dos n´os c e f

para resp ectivamente 9 e 4 (b). As demais etapas apresentadas nessa ﬁgura completam a

ilustra¸c˜ao do m´etodo de Prim.

O m´etodo de Prim ´e implementado pelo Algoritmo 2 e sua prova de corretude ´e

apresentada em Cormen et al. [12]. As opera¸c˜oes t´ıpicas de uma ﬁla de prioridades s˜ao

mostradas abaixo:

• Insert(i, p): insere o ´ıtem i na ﬁla, com prioridade p.

• RetrieveKey(i): retorna a prioridade do ´ıtem i.

• DecreaseKey(i, p): altera a prioridade do ´ıtem i para o valor p. Esta opera¸c˜ao

2.2 Algoritmos 9

requer que a nova prioridade seja maior (i.e. de menor valor) que a prioridade atual.

• ExtractMin(): remove e retorna o ´ıtem da ﬁla com a maior prioridade (i.e. o menor

valor para p).

Algoritmo 2 M´etodo de Prim

Entrada: Grafo G = (V, E) organizado em uma lista de adjacˆencias, um n´o raiz r e os

custos w.

{H: ﬁla de prioridades}

{π: armazena para cada v´ertice v ∈ V o v´ertice u ∈ V tal que (u, v) ∈ E



}

1: para todo v ∈ V fa¸ca

2: π[v] ← NIL;

3: Insert(v, ∞);

4: ﬁm para

5: DecreaseKey(r, 0);

6: enquanto H = ∅ fa¸ca

7: u ← ExtractMin();

8: para todo v adjacente a u fa¸ca

9: se v ∈ H e RetrieveKey(u) + w(u, v) < RetrieveKey(v) ent˜ao

10: π[v] ← u;

11: DecreaseKey(v, RetrieveKey(u) + w(u, v));

12: ﬁm se

13: ﬁm para

14: ﬁm enquanto

A complexidade do Algoritmo 2 depende do qu˜ao eﬁciente pode ser implementada

uma estrutura do tipo ﬁla de prioridades. O Cap´ıtulo 6 de Cormen et al. [12] desenvolve e

analisa a estrutura de dados binary heap (heap bin´ario), capaz de executar cada opera¸c˜ao

acima em O(log n), excetuando-se a opera¸c˜ao RetrieveKey, que pode ser facilmente im-

plementada em O(1). Usando um heap bin´ario, o algoritmo acima possui complexidade

O(m log n) [12].

Uma estrutura ainda mais eﬁciente ´e apresentada no Cap´ıtulo 20 de Cormen et al. [12].

Esta ﬁla de prioridades ´e conhecida por Fibonacci Heap [19] e ´e capaz de executar a op e-

ra¸c˜ao DecreaseKey em tempo O(1) amortizado. Assim, a complexidade do Algoritmo 2

torna-se O(m + n log n) [12]. Embora de grande interesse te´orico, os heaps de Fibonacci

s˜ao estruturas muito complexas para serem implementadas de maneira eﬁciente – s˜ao

desconhecidos resultados pr´aticos superiores `aqueles alcan¸cados por heaps bin´arios.

2.3 Resumo do Cap´ıtulo 10

Este cap´ıtulo apresentou o problema da ´arvore geradora m´ınima em grafos, bem como os

algoritmos de Kruskal [33] e de Prim [37]. Tamb´em foram apresentadas as estruturas de

dados para manuten¸c˜ao e atualiza¸c˜ao de uma ﬁla de prioridades (ou heap) e de conjuntos

disjuntos (ou set-union).

Este cap´ıtulo aborda o problema da ´arvore geradora m´ınima em grafos dinˆamicos. Para

isso, na Se¸c˜ao 3.1 ´e apresentado o problema das ´arvores dinˆamicas e as estruturas de

dados propostas para resolvˆe-lo. Essas estruturas s˜ao ´uteis no armazenamento de ´arvores

geradoras m´ınimas sujeitas a altera¸c˜oes dinˆamicas. Na Se¸c˜ao 3.2 s˜ao analisadas todas as

altera¸c˜oes que podem ocorrer em uma AGM quando o grafo ´e modiﬁcado. Por ﬁm, ´e

apresentada a revis˜ao bibliogr´aﬁca do problema de ´arvores geradoras m´ınimas em grafos

dinˆamicos.

O Problema das

Arvores Dinˆamicas, tamb´em conhecido como Dynamic Trees Problem ou

Linking and Cutting Trees Problem, foi proposto por Sleator e Tarjan [41]. Esse problema

introduz a necessidade de uma estrutura de dados para manter uma cole¸c˜ao de ´arvores

disjuntas sujeitas a dois tipos b´asicos de op era¸c˜oes: link e cut. A primeira opera¸c˜ao

combina duas ´arvores em uma s´o atrav´es da inser¸c˜ao de uma aresta, enquanto que a

segunda divide uma ´arvore em duas atrav´es da remo¸c˜ao de uma aresta.

As seguintes opera¸c˜oes foram propostas em [41] para dar suporte ao problema das

´arvores dinˆamicas:

• Link(u, v, c): une, atrav´es da aresta (u, v), a ´arvore enraizada em u com a ´arvore

que cont´em o v´ertice v. Esta opera¸c˜ao resultar´a em uma ´unica ´arvore onde o v´ertice

u, que antes n˜ao tinha um n´o pai, passa a ter v como pai. Essa aresta ter´a custo c.

• Cut(u, v): separa a ´arvore que cont´em os v´ertices u e v atrav´es da remo¸c˜ao da

3.1

Arvores Dinˆamicas 12

aresta (u, v).

• Root(v): retorna a raiz da ´arvore `a qual o v´ertice v p ertence.

• Cost(u, v): retorna o custo da aresta (u, v).

• Find_min(v) (resp. Find_max(v)): retorna a aresta de menor (resp. maior) custo

no caminho entre o v´ertice v e a raiz da sua ´arvore. Se v for a pr´opria raiz, esta

fun¸c˜ao retornar´a um valor nulo. Se houverem arestas m´ınimas (resp. m´aximas) de

mesmo custo no caminho at´e a raiz, a aresta mais pr´oxima da raiz ´e retornada.

• Update(v, c): atualiza os custos de todas as arestas no caminho entre v e a raiz da

´arvore, adicionando o valor c ao custo de cada aresta.

• Evert(v): altera a ´arvore contendo o v´ertice v, transformando v na raiz dessa

´arvore.

Basicamente, conforme as opera¸c˜oes de link e cut s˜ao executadas dinamicamente, es-

truturas de dados para ´arvores dinˆamicas devem oferecer meios para responder perguntas

sobre a rela¸c˜ao de pertinˆencia entre um v´ertice e uma ´arvore. Por exemplo, a qualquer mo-

mento pode-se perguntar a qual ´arvore pertence o v´ertice v atrav´es da opera¸c˜ao Root(v).

Outra pergunta freq

uente ´e a rela¸c˜ao entre dois v´ertices arbitr´arios u e v perante as ´ar-

vores dinˆamicas, ou seja, esses n´os pertencem `a mesma ´arvore? Essa resposta ´e dada

pela opera¸c˜ao Connected(u, v) ou pela compara¸c˜ao Root(u) = Root(v), que consiste

em perguntar se a raiz da ´arvore que cont´em o v´ertice v ´e a mesma raiz da ´arvore que

cont´em o v´ertice u. A terceira opera¸c˜ao freq

uente em ´arvores dinˆamicas est´a relacionada

aos caminhos dessa ´arvore, onde a opera¸c˜ao Find_min(v) (resp. Find_max(v)) retorna a

aresta de menor (resp. maior) custo no caminho entre os v´ertices v e u = Root(v).

Em suma, uma estrutura de dados para ´arvores dinˆamicas deve armazenar as arbo-

rescˆencias ou ´arvores que s˜ao dinamicamente modiﬁcadas, bem como oferecer suporte `as

opera¸c˜oes acima explicitadas. As pr´oximas trˆes se¸c˜oes apresentam as estruturas de dados

que d˜ao suporte `as opera¸c˜oes acima. Um resumo comparativo com as principais carac-

ter´ısticas de cada uma das ´arvores dinˆamicas existentes na literatura ´e apresentado na

Se¸c˜ao 3.1.1. Na Se¸c˜ao 3.1.2 ´e apresentada uma implementa¸c˜ao direta de ´arvores dinˆa-

micas e, por isso, ingˆenua e simplista, o que resulta em complexidades maiores a custos

constantes reduzidos. Por ﬁm, na Se¸c˜ao 3.1.3) ´e introduzida uma estrutura cl´assica de

´arvores dinˆamicas, prop osta por Sleator e Tarjan [41]. Essa estrutura de dados garante

3.1

Arvores Dinˆamicas 13

complexidades menores a custos constantes maiores por opera¸c˜ao, j´a que possui organi-

za¸c˜ao interna mais complexa que a primeira, o que ´e um efeito colateral da garantia de

complexidade logar´ıtmica por opera¸c˜ao.

Algumas das estruturas de dados usadas para a representa¸c˜ao de ´arvores dinˆamicas s˜ao

apresentadas e referenciadas abaixo:

• RD-trees: simples e de f´acil implementa¸c˜ao; oferece, no pior caso, opera¸c˜oes rela-

cionadas a caminhos com complexidades lineares. Por outro lado, o restante das

opera¸c˜oes pode ser executado em tempo constante.

• ST-trees [41]: embora seja uma estrutura complexa, garante complexidades de or-

dem logar´ıtmica por opera¸c˜ao. Existem implementa¸c˜oes onde essa complexidade ´e

de pior caso e implementa¸c˜oes onde essa complexidade ´e amortizada.

• Topology trees [17, 18]: ´arvores top ol´ogicas baseadas em agrupamento (clusteriza-

¸c˜ao) de v´ertices, resultando em grupos de arestas que s˜ao mapeados em uma ´arvore

balanceada, garantindo assim complexidade logar´ıtmica por opera¸c˜ao. Contudo, sua

implementa¸c˜ao ´e complexa e suporta apenas ´arvores com n´os de grau m´aximo trˆes.

• ET-trees [26, 27]: tamb´em conhecidas como Euler tour trees, n˜ao oferecem opera-

¸c˜oes para consultas a caminhos, como por exemplo para a obten¸c˜ao da aresta de

menor custo no caminho entre dois v´ertices. Mesmo assim, s˜ao uma boa op¸c˜ao para

consultas sobre a conectividade entre dois n´os (veriﬁcar se dois n´os u e v perten-

cem `a mesma ´arvore). Sua implementa¸c˜ao ´e relativamente simples e ainda fornece

complexidade logar´ıtmica para to das as opera¸c˜oes dispon´ıveis.

• Top trees [2, 3, 31]: s˜ao ´arvores muito parecidas com as ´arvores topol´ogicas de

Frederickson [17, 18], j´a que tamb´em s˜ao baseadas em clusteriza¸c˜oes (mais espe-

ciﬁcamente, parti¸c˜oes topol´ogicas do conjunto de n´os da ´arvore). Por outro lado,

estendem as topology trees de forma a aceitarem ´arvores de grau ilimitado. Ainda,

sua parti¸c˜ao topol´ogica permite o uso de algoritmos simples, baseados em divis˜ao-

e-conquista. As top trees tamb´em oferecem opera¸c˜oes com complexidade O(log n),

j´a que s˜ao baseadas em ´arvores bin´arias balanceadas.

3.1

Arvores Dinˆamicas 14

• RC-trees [1]: tamb´em denominadas rake-and-compress trees, s˜ao ´arvores dinˆamicas

baseadas em contra¸c˜oes [35].

E uma estrutura mais simples que as ´arvores topol´o-

gicas, mas assim como elas, suporta apenas ´arvores com n´os de grau m´aximo trˆes.

• Self-adjusting top trees [47]: este trabalho prop˜oe o uso de estruturas de dados auto-

ajust´aveis [42, 43] (i.e., n˜ao possuem mecanismos r´ıgidos de balanceamento, j´a que

quando a ´arvore ´e acessada certas rotinas de ajuste s˜ao executadas) para estender

as top trees.

De maneira geral, pode-se concluir que todas as ´arvores acima citadas excetuando-se

as RD-trees possuem um ´unico objetivo: mapear uma ´arvore arbitr´aria em uma ´arvore

balanceada de forma a garantir complexidades logar´ıtmicas [47]. As ET-trees realizam essa

tarefa de maneira elegante, mas n˜ao d˜ao suporte a opera¸c˜oes relacionadas a caminhos.

J´a as ST-trees representam as ´arvores balanceadas a partir de caminhos extra´ıdos das

´arvores arbitr´arias, o que resulta em uma estrutura compacta e eﬁciente; contudo, n˜ao

fornecem op era¸c˜oes em sub-´arvores.

Arvores topol´ogicas e RC-trees representam ´arvores

arbitr´arias a partir de contra¸c˜oes, mas s˜ao funcionais apenas em ´arvores tern´arias, bin´arias

ou un´arias. Por ﬁm, top trees e self-adjusting top trees procuram eliminar a exigˆencia de

´arvores com n´os de grau limitado, mas ainda n˜ao existem implementa¸c˜oes eﬁcientes para

as mesmas.

As Se¸c˜oes 3.1.2 e 3.1.3 descrevem duas das principais estruturas de dados para ´arvores

dinˆamicas citadas acima, respectivamente RD-trees e ST-trees .

As RD-trees s˜ao uma estrutura de dados extremamente simples. N˜ao h´a na literatura uma

referˆencia a essa estrutura; sabe-se que seu surgimento ocorreu atrav´es de adapta¸c˜oes `a

estrutura de dados para ´arvores reversas (reversed trees), utilizadas no algoritmo set-

union [46].

Estruturas de ´arvores reversas conectam um n´o u ao n´o v de forma orientada, atrav´es

de um arco (u, v). Nesse caso, diz-se que v ´e pai de u, originando assim o nome de ´arvores

reversas, visto que tradicionalmente um n´o possui ponteiros para seus ﬁlhos ao inv´es de um

´unico ponteiro para seu pai. Sob a ´otica computacional, um n´o u ∈ V de uma estrutura

de ´arvores reversas T = (V, E



) deve possuir os campos π[u], onde ser´a armazenado o n´o

v ∈ V correspondente ao pai de u, e ω[u], referente ao custo do arco conectando o n´o u

ao seu pai.

3.1

Arvores Dinˆamicas 15

Cabe ressaltar que neste trabalho ser´a usada a nota¸c˜ao arco, ao inv´es de aresta, quando

houver referˆencia a estruturas de dados orientadas, como ´e o caso das ´arvores reversas. A

Figura 3.1 ilustra uma AGM (a) e sua ´arvore reversa (b).

(a) AGM (b)

Arvore reversa

Figura 3.1: Uma AGM mapeada por uma ´arvore reversa.

Uma implementa¸c˜ao simples e direta da estrutura de dados RD-trees pode ser obtida

a partir de um vetor π com n posi¸c˜oes: se cada n´o ´e identiﬁcado por uma chave ´unica no

intervalo [1, n], ent˜ao π[u], u ∈ {1 . . . n} pode armazenar o inteiro equivalente ao pai de u

na ´arvore T = (V, E



). Ainda, o inteiro 0 pode ser usado para indicar a ausˆencia de um

pai para um n´o arbitr´ario r ∈ {1 . . . n}, n´o este que recebe a denomina¸c˜ao especial de n´o

raiz. Para armazenar os custos de cada arco (u, v), pode-se utilizar o vetor ω, tamb´em

com n posi¸c˜oes. Nesse vetor, ω[u] indicaria o custo do arco (u, π[u]).

Nessa estrutura, onde cada ´arvore disjunta ´e representada por uma ´arvore reversa, as

opera¸c˜oes propostas por Sleator e Tarjan [41] podem ser assim implementadas:

• Link(u, v, c): basta veriﬁcar se π[u] = 0 para determinar se o n´o u ´e realmente uma

raiz. Em caso aﬁrmativo, a opera¸c˜ao π[u] ← v estabelece a liga¸c˜ao (u, v) enquanto

a opera¸c˜ao ω[u] ← c ajusta o custo desse arco. Esta tarefa tem custo constante.

• Cut(u, v): inicialmente, deve-se veriﬁcar a existˆencia do arco (v, u) ou do arco (u, v).

O arco (v, u) existe quando a condi¸c˜ao π[v] = u ´e satisfeita; j´a a existˆencia do arco

(u, v) ´e veriﬁcada quando π[u] = v. Caso a primeira condi¸c˜ao seja constatada, o

corte ´e estabelecido atrav´es da opera¸c˜ao π[v] ← 0; j´a em caso contr´ario corta-se o

arco atrav´es da opera¸c˜ao π[u] ← 0. Por ﬁm, atualiza-se o vetor ω com um valor

especial indicando a ausˆencia desse arco. A complexidade desta opera¸c˜ao ´e O(1).

• Root(v): a raiz da ´arvore que cont´em o n´o v pode ser obtida ao subir pela ´arvore

at´e que π[u] = 0; nesse caso a raiz da ´arvore onde se encontra o n´o v seria o n´o

3.1

Arvores Dinˆamicas 16

u. Podem existir ´arvores lineares, o que resulta em complexidade linear para que a

subida na ´arvore seja realizada.

• Cost(u, v): se π[u] = v, retorna-se ω[u]. Se π[v] = u, ent˜ao retorna-se ω[v]. Quando

nenhuma das igualdades acima ´e satisfeita, o arco (u, v) n˜ao existe e um valor

especial indicando tal ausˆencia ´e retornado. Essa opera¸c˜ao tem complexidade O(1).

• Find_min(v): esta opera¸c˜ao ´e praticamente igual `a opera¸c˜ao Root(v), com a ex-

ce¸c˜ao de se salvar o arco de menor custo durante a subida na ´arvore. Assim, sua

complexidade tamb´em ´e O(n).

• Update(v, c): ao inv´es de armazenar o arco de menor custo durante a subida na

´arvore, como ´e feito na opera¸c˜ao Find_min(v), aqui o valor c ´e adicionado ao valor

de ω correspondente aos arcos percorridos durante a subida pela ´arvore. A comple-

xidade de uma chamada a esse m´etodo ´e O(n).

• Evert(v): esta opera¸c˜ao, que realiza a troca de ra´ızes em RD-trees, ´e detalhada no

Algoritmo 3.

Algoritmo 3 Evert(v) para a estrutura de dados RD-trees

Entrada: O novo n´o raiz v e a estrutura de dados RD-trees T = (V, E



1: p ← π[v];

2: se p = 0 ent˜ao

3: retorne 0;

4: ﬁm se

5: Evert(p);

6: π[p] ← v;

7: π[v] ← 0;

8: ω[p] ← ω[v];

A execu¸c˜ao do Algoritmo 3 ´e recursiva. Seu caso base ocorre quando um n´o raiz p ´e

atingido, para ent˜ao as opera¸c˜oes das linhas 6 − 8 transformarem o n´o v, que se encontra

no topo da pilha de recursividade, na nova raiz da ´arvore e fazendo do antigo n´o raiz p

um ﬁlho de v. Ao ﬁm da pilha, o n´o v da primeira chamada recursiva ´e transformado em

um n´o raiz.

O Algoritmo 3 tem seu pior caso dado pela existˆencia de uma ´arvore linear contendo

n n´os. Neste caso, s˜ao feitas n − 1 chamadas recursivas com custo O(1) cada, resultando

na complexidade de O(n) .

Exemplos das opera¸c˜oes acima s˜ao mostrados na Figura 3.2. Em (a) e (b), a opera¸c˜ao

Link(c, b); em (c) e (d), a opera¸c˜ao Cut(c, b); e em (e), a opera¸c˜ao Evert(f).

3.1

Arvores Dinˆamicas 17

(a) T = T

∪ T

(b) Opera¸c˜ao Link(c, b)

(d) Opera¸c˜ao Cut(c, b)

(e) Opera¸c˜ao Evert(f )

Figura 3.2: Opera¸c˜oes em uma estrutura de dados RD-trees T = (V, E



As ST-trees s˜ao ´arvores dinˆamicas propostas por Sleator e Tarjan [41], com aplica¸c˜oes em

algoritmos eﬁcientes para situa¸c˜oes como:

• determinar ﬂuxo m´aximo em redes;

• calcular ´arvores geradoras m´ınimas com restri¸c˜oes; e

• resolver o algoritmo simplex para redes.

Intuitivamente, as ST-trees representam os caminhos das ´arvores dinˆamicas, de al-

turas indeﬁnidas (e possivelmente lineares no pior caso), atrav´es de ´arvores balanceadas,

garantindo assim complexidades de ordem logar´ıtmica para as opera¸c˜oes sobre ´arvores

3.1

Arvores Dinˆamicas 18

dinˆamicas. Para tanto, esta estrutura classiﬁca arbitrariamente os arcos de cada ´arvore

em cont´ınuos ou descont´ınuos, onde no m´aximo um arco incidente em cada n´o v ∈ T pode

ser cont´ınuo, para ent˜ao deﬁnir uma cole¸c˜ao de caminhos disjuntos formados por arestas

cont´ınuas.

(a)

Arvore reversa (b) Particionamento

Figura 3.3: Um exemplo de AGM e seu particionamento em caminhos.

A Figura 3.3, que ilustra uma poss´ıvel classiﬁca¸c˜ao dos arcos de uma ´arvore disjunta

representando uma AGM, possui as seguintes deﬁni¸c˜oes: os arcos (d, f) e (c, b) s˜ao arcos

descont´ınuos, enquanto que os arcos restantes s˜ao cont´ınuos. O caminho (g, f), (f, b) e

(b, a) ´e denominado caminho-raiz (root path) e deve ser ´unico, dado que o ´unico n´o raiz

de uma ´arvore pode ser incidido apenas por uma aresta cont´ınua.

O pr´oximo passo ´e representar cada caminho cont´ınuo implicitamente, atrav´es de uma

´arvore balanceada. Assim, cada ´arvore disjunta ´e mapeada por uma ´arvore balanceada,

que por conseguinte ´e mapeada, usando seu n´o raiz como chave, por uma ´arvore balance-

ada global (as ´arvores balanceadas que representam as ´arvores dinˆamicas s˜ao unidas com

base em seus caminhos). Para isso, Sleator e Tarjan sugerem o uso de ´arvores de busca

tern´arias (biased search trees), propostas por Bent et al. [5], que garantem complexidade

de ordem logar´ıtmica inclusive para opera¸c˜oes de pior caso.

Em [41] s˜ao apresentadas duas poss´ıveis implementa¸c˜oes de ST-trees. De acordo com

o esquema de particionamento adotado suas complexidades podem ser amortizadas ou de

pior caso, sempre de ordem logar´ıtmica em n. A escolha da ´arvore balanceada para ma-

pear os caminhos cont´ınuos tamb´em pode resultar em complexidades diferentes: ´arvores

bin´arias de busca (binary search trees) resultariam em uma estrutura com complexidade

O(log

n) por opera¸c˜ao; ´arvores bin´arias de busca auto-ajust´aveis [43] (self-adjusting bi-

nary search trees ou splay trees) resultariam em ST-trees de complexidade amortizada

O(log n) por opera¸c˜ao, por´em facilitariam sua implementa¸c˜ao.

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 19

Esta se¸c˜ao apresenta as principais estruturas de dados e algoritmos propostos para pro-

blemas dinˆamicos. A Se¸c˜ao 3.2.1 analisa os principais aspectos de um problema dinˆamico,

com foco no problema da AGM. Em seguida, ´e realizado um minucioso estudo dos al-

goritmos e estruturas de dados propostos para esse problema, considerando cada tipo de

altera¸c˜ao que possa ocorrer em tais grafos.

O problema em quest˜ao consiste em manter a ´arvore geradora m´ınima de um grafo sujeito

a constantes mudan¸cas. Essas mudan¸cas s˜ao divididas em trˆes classes: inser¸c˜oes e remo-

¸c˜oes de v´ertices, inser¸c˜oes e remo¸c˜oes de arestas e, por ﬁm, atualiza¸c˜oes – incrementos

ou decrementos – em custos de arestas. Com rela¸c˜ao a essas opera¸c˜oes, um algoritmo

ou estrutura de dados ´e dito totalmente dinˆamico se uma dessas classes de altera¸c˜oes ´e

totalmente suportada. Se apenas uma opera¸c˜ao (i.e., apenas incrementos em custos de

arestas, ou apenas inser¸c˜oes de v´ertices) ´e suportada, esse algoritmo ´e dito semi-dinˆamico

ou parcialmente dinˆamico. Ainda, um algoritmo parcialmente dinˆamico ´e dito incremen-

tal se apenas inser¸c˜oes s˜ao suportadas, e decremental se apenas remo¸c˜oes s˜ao suportadas.

Diz-se que um algoritmo ´e on-line quando as altera¸c˜oes s˜ao processadas em tempo real

(i.e., n˜ao h´a pr´e-processamento, ou seja, as atualiza¸c˜oes s˜ao processadas em ordem, uma

ap´os a outra).

Abaixo s˜ao apresentadas as poss´ıveis mudan¸cas que uma AGM pode sofrer quando

seu grafo original (Figura 3.4) ´e alterado.

Figura 3.4: Grafo G = (V, E) e sua AGM T = (V, E



Na Figura 3.5 s˜ao apresentados trˆes poss´ıveis casos de inser¸c˜oes e remo¸c˜oes de v´ertices.

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 20

(a) Inser¸c˜ao do v´ertice h (b) Remo¸c˜ao do v´ertice b (c) Remo¸c˜ao do v´ertice g

Figura 3.5: AGMs resultantes de inser¸c˜oes e remo¸c˜oes de v´ertices em G.

Em (a), o grafo G ´e modiﬁcado atrav´es da inser¸c˜ao de um v´ertice h e um conjunto de

arestas {(e, h), (g, h)}. Remo¸c˜oes de v´ertices s˜ao apresentados em (b) e (c), onde os

v´ertices b em (b), e g em (c), juntamente com suas respectivas arestas incidentes, s˜ao

removidos do grafo inicial G.

(a) Inser¸c˜ao da aresta (c, f ) (b) Remo¸c˜ao da aresta (b, f) (c) Remo¸c˜ao da aresta (e, f )

Figura 3.6: AGMs resultantes de inser¸c˜oes e remo¸c˜oes de arestas em G.

A Figura 3.6 apresenta trˆes das poss´ıveis altera¸c˜oes na AGM causadas por inser¸c˜oes

(a) e por remo¸c˜oes de arestas (b) e (c). Em (a) a aresta (c, f) com custo 1 ´e inserida,

reﬂetindo na AGM T a necessidade de remo¸c˜ao da aresta (b, c). Outro caso pode ser

formulado a partir da situa¸c˜ao (a), onde a mesma aresta (c, f) seria inserida com custo

7 ao inv´es de 1. Nesse caso a AGM n˜ao seria modiﬁcada. Por outro lado, a remo¸c˜ao de

uma aresta (u, v) s´o altera a ´arvore geradora m´ınima T se (u, v) ∈ T , como pode ser visto

em (b), onde a remo¸c˜ao de (b, f) causa altera¸c˜oes em T ; em caso contr´ario, T permanece

inalterada, como exempliﬁcado em (c), onde a remo¸c˜ao da aresta (e, f) n˜ao reﬂete em T .

Dois fatos resultam da inser¸c˜ao e remo¸c˜ao de arestas em grafos dinˆamicos:

Fato 3.1 A inser¸c˜ao em G da aresta arbitr´aria (u, v) resultar´a em altera¸c˜oes na AGM

T = (V, E



) se e somente se existir uma aresta (x, y) no ciclo induzido pela inser¸c˜ao de

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 21

(u, v) em T tal que w(x, y) > w(u, v). Nesse caso, a nova AGM ser´a T = (V, (E



−

{(x, y)}) ∪ {(u, v)}).

Fato 3.2 A remo¸c˜ao de G da aresta arbitr´aria (u, v) causar´a modiﬁca¸c˜oes na AGM T =

(V, E



) se e somente se (u, v) ∈ E



. Tomando T

= (V

, E



) e T

= (V

, E



) como as

duas ´arvores resultantes da remo¸c˜ao da aresta (u, v), deve-se encontrar a aresta de custo

m´ınimo (x, y) tal que x ∈ V

e y ∈ V

. Caso essa aresta n˜ao exista, T n˜ao mais ser´a uma

´arvore geradora m´ınima, mas sim uma ﬂoresta geradora m´ınima (FGM, ou Minimum

Spanning Forest – MSF).

(a) Incremento no custo de (d, f) (b) Decremento no custo de (e, f)

Figura 3.7: AGMs resultantes de mudan¸cas no custo de arestas.

Mudan¸cas nos custos podem ocorrer atrav´es de opera¸c˜oes de incremento ou decre-

mento no custo de uma aresta, como ilustrado nas Figuras 3.7 (a) e (b), respectivamente.

Deve-se lembrar que, se o grafo G = (V, E) possui uma AGM T = (V, E



), opera¸c˜oes

de incremento e decremento n˜ao desconectam essa ´arvore (i.e., a AGM sempre existir´a)

– apenas seu custo pode ser alterado. Incrementos e decrementos em custos de arestas

resultam nos seguintes fatos:

Fato 3.3 O incremento no custo da aresta arbitr´aria (u, v) resultar´a em mudan¸cas na

AGM T = (V, E



) se e somente se (a) (u, v) ∈ E



e (b) existir uma aresta (x, y) conectando

as ´arvores T

e T

resultantes da remo¸c˜ao de (u, v) tal que w(x, y) < w(u, v).

Fato 3.4 O decremento no custo da aresta arbitr´aria (u, v) causar´a altera¸c˜oes na AGM

T = (V, E



) se e somente se (a) (u, v) /∈ T e (b) existe uma aresta (x, y) no ciclo induzido

pela aresta (u, v) em T tal que w(x, y) > w(u, v). Nesse caso, a nova AGM ´e dada por



= (V, (E



− {(x, y)}) ∪ {(u, v)} ).

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 22

Os Fatos 3.1, 3.2, 3.3 e 3.4 s˜ao baseados nas seguintes propriedades de uma ´arvore

geradora m´ınima T = (V, E



) com rela¸c˜ao ao grafo G = ( V, E) [32]:

(i) Propriedade do ciclo: para cada ciclo C em G, a aresta de maior custo em C n˜ao

faz parte de T .

(ii) Propriedade do corte: para qualquer subconjunto X ⊆ V n˜ao vazio de v´ertices, a

aresta de menor custo (u, v) ∈ E tal que u ∈ X e v /∈ X pertence `a AGM T .

Spira e Pan [44] foram os primeiros a estudar os problemas para manuten¸c˜ao de propri-

edades de grafos sujeitos a altera¸c˜oes dinˆamicas. Em [44] foi proposto um procedimento

que atualiza uma AGM T = (V, E



) ap´os a inser¸c˜ao no grafo G = (V, E) do v´ertice v e

do conjunto de arestas {(v, x) | x ∈ V }. O novo conjunto de v´ertices ap´os a inser¸c˜ao

´e V



= V ∪ {v}, enquanto que o novo conjunto de arestas ´e F = E ∪ {(v, x) | x ∈ V }.

Este procedimento ´e descrito no Algoritmo 4.

Algoritmo 4 Algoritmo de Spira e Pan para inser¸c˜ao de n´os.

Entrada: O grafo formado pela AGM T = (V, E



), o novo v´ertice v e as novas arestas

adjacentes a v.

1: V



= V ∪ {v};

2: E



= {∅};

3: Armazenar em E



a aresta de menor custo incidente em cada n´o de V



;

4: Encontrar as componentes conexas do grafo formado por V



e E



;

5: Encontrar a aresta de menor custo incidente em cada componente acima;

6: Compactar em um ´unico n´o cada uma das componentes conexas acima;

7: Voltar ao passo 3 caso exista mais de um n´o;

8: retorne T = (V



, E



);

Teorema 3.5 [44] O Algoritmo 4 atualiza a ´arvore geradora m´ınima com complexidade

O(|V



|) = O(n).

Prova Seja |V



| = n



= n + 1. O passo 3 requer no m´aximo 4n



compara¸c˜oes. As

componentes conexas (passo 4) podem ser encontradas em O(n



) usando o algoritmo de

Tarjan [45]. O passo 5 pode ser executado em O(n



) se forem processadas apenas as

arestas n˜ao analisadas no passo 3. O passo 6 ´e trivial, resultando em um grafo com no

m´aximo a metade do n´umero de v´ertices existentes no grafo atual. Assim, a recurs˜ao

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 23

T (n



) ´e resolvida pela equa¸c˜ao

T (n



) ≤ T (n



/2) + cn



T (n



) = O(n). (3.6)

Um exemplo da aplica¸c˜ao do Algoritmo 4 ´e ilustrado pela Figura 3.8

Outros resultados de Spira e Pan [44] dizem respeito a altera¸c˜oes em custos de arestas,

onde s˜ao provados os limites superiores de O(n

) arestas a serem analisadas ap´os um

incremento de custo e O(n) arestas a serem analisadas ap´os um decremento de custo, e a

remo¸c˜ao de n´os, onde ´e provado o limite de O(n

) para a atualiza¸c˜ao de T .

Ainda, Chin e Houck [11] apresentam um algoritmo tamb´em linear em n para a

inser¸c˜ao de n´os e um algoritmo que determina em O(n

) todas as poss´ıveis solu¸c˜oes para

a remo¸c˜ao de qualquer v´ertice de T .

Por ﬁm, Das e Loui [13] prop˜oem um algoritmo semi-dinˆamico decremental (somente

a remo¸c˜ao de n´os ´e considerada).

E fornecido um algoritmo que atualiza a AGM T em

O(mα(m, n)) se assumida a ordena¸c˜ao pr´evia das arestas por seus custos; em caso con-

tr´ario a complexidade ´e de O(m log n), o que n˜ao melhora a execu¸c˜ao de um algoritmo

est´atico (cl´assico). Em [13] tamb´em ´e apresentado um algoritmo paralelo com complexi-

dade O(log

n) quando utilizados m processadores em uma CREW PRAM (Concurrent

Reading and Exclusive Writing Parallel Random Access Machine).

Algoritmos para atualiza¸c˜ao de ´arvores geradoras m´ınimas ap´os a inser¸c˜ao ou remo¸c˜ao

de arestas foram propostos em [16, 17, 18, 26, 31]. Estes trabalhos s˜ao apresentados nas

se¸c˜oes seguintes.

As ´arvores topol´ogicas ou Topology Trees foram propostas por Frederickson [17] com

base em uma t´ecnica denominada clusteriza¸c˜ao. Com esta t´ecnica, os v´ertices da AGM

T = (V, E



) s˜ao particionados em grupos de sub-´arvores conexas, de forma que cada grupo

tenha poucas sub-´arvores adjacentes. Uma ´arvore topol´ogica consiste em representar

a AGM usando uma ´arvore 1-2-3-4 balanceada, com altura logar´ıtmica, formada por

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 24

(a) Inser¸c˜ao de h (b) Passo 3

(e) Passo 6 (f) Grafo resultante

(g) Resultado da recurs˜ao (h) Resultado do algoritmo

Figura 3.8: Execu¸c˜ao do algoritmo de Spira e Pan [44] para a inser¸c˜ao do v´ertice h.

clusteriza¸c˜oes recursivas. Adicionalmente, as arestas pertencentes ao subconjunto E − E



podem ser mantidas em uma ´arvore topol´ogica bidimensional (2-d topology tree). Uma

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 25

´arvore topol´ogica ´e detalhada pela Figura 3.9.

(a) Grafo original G (b) Ternariza¸c˜ao (c) AGM T de G

(d) Agrupamento 1 (e) Divis˜ao do grupo 1 (f) Divis˜ao dos grupos 2 e 3

(g)

Arvore topol´ogica de G

Figura 3.9: Um grafo e sua respectiva ´arvore topol´ogica.

Nessa estrutura, ´arvores geradoras m´ınimas podem ser mantidas por ´arvores topo-

l´ogicas bidimensionais com complexidade O(m

1/2

) [17, 18]. Algoritmos mais simples,

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 26

que fazem uso apenas de ´arvores topol´ogicas, atualizam uma AGM com complexidade

O((m log m)

1/2

) [21, 40]. Se apenas a t´ecnica de clusteriza¸c˜ao ´e empregada, algoritmos

podem ser implementados com complexidade O(m

2/3

Os algoritmos propostos por Frederickson [17, 18] s˜ao usuais apenas em grafos com

v´ertices de grau m´aximo trˆes. Com isso, sua utiliza¸c˜ao ´e complicada pela necessidade de

convers˜ao dos grafos que n˜ao satisfazem esta exigˆencia. Ainda assim, um algoritmo para

tal convers˜ao ´e apresentado em [22].

Esparsiﬁca¸c˜ao [16] ´e uma t´ecnica utilizada para melhoria de algoritmos que n˜ao requer

que estes sejam especiﬁcamente desenvolvidos para se beneﬁciar da mesma. Essa t´ecnica

faz com que algoritmos com complexidades dependentes do n´umero de arestas do grafo

passem a ter complexidades de grafos esparsos, ou seja, reduzidas de um fator O(m) para

O(n). Mais especiﬁcamente, algoritmos dinˆamicos com complexidade T (n, m) para grafos

com n v´ertices e m arestas passam a ter complexidade T (n, O(n)) log(m/n) ou T (n, O(n)),

dependendo da t´ecnica de esparsiﬁca¸c˜ao utilizada – simples ou otimizada. Por exemplo, os

algoritmos de Frederickson [17], de complexidade O(m

1/2

), tem complexidade de O(n

1/2

)

ao se usar a vers˜ao otimizada de esparsiﬁca¸c˜ao, aplicando-se esses algoritmos diretamente

sobre os grafos esparsos gerados pela t´ecnica.

A t´ecnica de esparsiﬁca¸c˜ao ´e relativamente simples: as arestas do grafo G = (V, E)

s˜ao particionadas em m/n grupos, cada um contendo exatamente n arestas, exceto o

´ultimo grupo. Cada grupo deve possuir um certiﬁcado, especiﬁcado na Deﬁni¸c˜ao 3.7, que

´e ent˜ao encapsulado em um n´o folha. Os n´os folha s˜ao ent˜ao agrupados dois a dois em

n´os-certiﬁcado, de forma a construir uma ´arvore bin´aria completa da base at´e o topo de

forma recursiva.

Deﬁni¸c˜ao 3.7 [16] Para qualquer propriedade P e grafo G = (V, E), um certiﬁcado

para G ´e um grafo G



= (V, E



) que, para qualquer grafo H = (V, F ), E ∪ F possui a

propriedade P se e somente se E



∪ F possuir a propriedade P.

A ´arvore de esparsiﬁca¸c˜ao simples do grafo da Figura 3.4 ´e apresentada na Figura 3.10.

Se uma atualiza¸c˜ao ´e realizada em qualquer aresta de G, no m´aximo log n n´os ser˜ao afe-

tados. Como cada n´o da ´arvore de esparsiﬁca¸c˜ao cont´em n arestas, a complexidade dessa

atualiza¸c˜ao do grafo original cai de O(m) para O(n log n), que corresponde `a aplica¸c˜ao

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 27

desse algoritmo sobre os log n n´ıveis da ´arvore de esparsiﬁca¸c˜ao ao custo de O(n) para

cada n´ıvel. A raiz dessa ´arvore armazena a solu¸c˜ao do problema para o grafo G.

Figura 3.10:

Arvore de esparsiﬁca¸c˜ao – para construir uma AGM no n´ıvel l (nesse caso

l = 0, o que corresponde ao n´o raiz da ´arvore de esparsiﬁca¸c˜ao) s´o s˜ao consideradas as

arestas que est˜ao nas AGMs dos ﬁlhos do n´o atual (nesse caso, no n´ıvel l = l + 1).

At´e a se¸c˜ao anterior, todos os m´etodos para atualiza¸c˜ao de ´arvores geradoras m´ınimas

eram baseados em uma ´unica estrutura de dados dinˆamica. Essa estrutura deve ser res-

pons´avel por tratar inser¸c˜oes e remo¸c˜oes de arestas de forma a manter uma AGM do

grafo dinˆamico. Contudo, essa abordagem chegou a seu limite te´orico com a introdu¸c˜ao

da t´ecnica de esparsiﬁca¸c˜ao. Em [16] foi provado que uma estrutura de dados para ma-

nuten¸c˜ao de AGMs n˜ao poderia mais suportar complexidades assintoticamente r´apidas

(lineares) sem pagar o pre¸co do armazenamento n˜ao-linear, um problema freq

uente em

estruturas de dados est´aticas que tamb´em se tornou um limitante para as estruturas de

dados dinˆamicas.

Desta forma, em [27] ´e apresentado o primeiro algoritmo randomizado de comple-

xidade polilogar´ıtmica para os problemas dinˆamicos de conectividade e ´arvore geradora

m´ınima aproximada. Para tanto, foram elaborados algoritmos e estruturas de dados que

utilizam ´arvores dinˆamicas mais simples e r´apidas, as ET-trees, ao inv´es de se utilizar uma

´unica e complexa estrutura de dados.

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 28

Seguindo a tendˆencia de se produzir algoritmos bem elaborados ao inv´es de comple-

xas estruturas de dados monol´ıticas, o algoritmo para manuten¸c˜ao de ´arvores geradoras

m´ınimas HK foi proposto por Henzinger e King [26].

Embora utilize uma abordagem completamente diferente daquela apresentada por

Frederickson [17, 18], a complexidade do algoritmo HK ´e de apenas O(n

1/3

log n) quando

amortizada sobre um m´ınimo de m opera¸c˜oes, o que n˜ao reduz signiﬁcativamente os limites

te´oricos impostos pela utiliza¸c˜ao de ´arvores topol´ogicas. Adicionalmente, os algoritmos

propostos s˜ao de dif´ıcil implementa¸c˜ao, e ainda requerem grafos com custos distintos,

introduzindo uma camada extra de diﬁculdade. Contudo, uma importante t´ecnica ´e pro-

posta nesse trabalho: a partir de um algoritmo semi-dinˆamico para remo¸c˜oes de arestas,

fez-se poss´ıvel transform´a-lo em um algoritmo totalmente dinˆamico atrav´es da cria¸c˜ao e

manuten¸c˜ao de s = log m estruturas semi-dinˆamicas.

Os algoritmos apresentados na pr´oxima se¸c˜ao fazem uso da t´ecnica proposta por Hen-

zinger e King [26] para compor um algoritmo com complexidade amortizada de O(log

para atualizar uma AGM.

O trabalho de Holm et al. [30, 31] trouxe os primeiros e ´unicos algoritmos determin´ısticos

de complexidade polilogar´ıtmica para os problemas de conectividade, ﬂoresta geradora

m´ınima e biconectividade. Todos os algoritmos determin´ısticos at´e ent˜ao apresentados

trazem complexidades maiores que a ordem linear de grandeza.

O algoritmo apresentado possui complexidade O(log

n) e ´e baseado no trabalho de

Henzinger e King [26], onde uma estrutura semi-dinˆamica ´e utilizada como base para

a composi¸c˜ao de uma estrutura totalmente dinˆamica. Tomando por base um algoritmo

que mant´em uma ﬂoresta geradora de um grafo dinˆamico (estrutura para manuten¸c˜ao de

conectividade), o algoritmo ent˜ao ´e especializado de modo a manter uma ﬂoresta geradora

m´ınima desse grafo, satisfazendo ent˜ao o problema aqui estudado.

Neste algoritmo para manuten¸c˜ao de conectividade em grafos dinˆamicos, uma ﬂoresta

geradora F deve ser mantida a partir do grafo G = (V, E). Projetada para fornecer

algoritmos com baixa complexidade amortizada, a t´ecnica proposta associa um n´ıvel l(u, v)

a cada aresta (u, v) ∈ E, com l(u, v) ≤ L = log n. Para cada n´ıvel i, F

deve armazenar a

ﬂoresta geradora para as arestas (u, v) ∈ E tal que l(u, v) ≥ i, implicando em F = F

⊇

⊇ F

. . . ⊇ F

. Os seguintes invariantes s˜ao mantidos:

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 29

(i) o n´umero m´aximo de n´os conectados em uma ´arvore F

´e n/2

. Isso resulta em

L ser o n´ıvel onde existe o maior n´umero de n´os conectados na estrutura.

(ii) F = (V, E



) ´e a maior ﬂoresta geradora de G = (V, E), ou seja, se (u, v) ∈ E − E



ent˜ao os v´ertices u e v j´a est˜ao conectados na ﬂoresta F do n´ıvel l(u, v), ou seja, F

l(u,v)

Inicialmente, como todas as arestas se encontram no n´ıvel mais baixo (l = 0), ambos

os invariantes acima s˜ao satisfeitos. A amortiza¸c˜ao ´e baseada no argumento que o n´ıvel

de uma aresta s´o pode ser incrementado L vezes e, para tanto, o n´ıvel de uma aresta

arbitr´aria nunca pode diminuir. Intuitivamente, uma aresta que n˜ao pertence a F deve

subir de n´ıvel quando seus v´ertices j´a est˜ao conectados em um n´ıvel mais alto da estrutura.

Os algoritmos para inser¸c˜ao e remo¸c˜ao de arestas s˜ao apresentados abaixo:

• Insert(u, v): a aresta ´e inserida no n´ıvel 0 da estrutura. Caso u n˜ao esteja conec-

tado a v em F , ent˜ao F

← F

∪ {(u, v)}.

• Delete(u, v): se (u, v) /∈ F , basta remover essa aresta da estrutura. Caso contr´ario,

uma aresta de reposi¸c˜ao deve ser encontrada, reconectando F no n´ıvel mais alto

poss´ıvel. Pela estrat´egia adotada para a aloca¸c˜ao das arestas em F , sabe-se que

esta aresta de reposi¸c˜ao se encontra no n´ıvel l ≤ l(u, v). Desta forma, o algoritmo

Replace(u, v, l(u, v)) faz a busca por uma aresta substituta.

• Replace(u, v, i): pela deﬁni¸c˜ao da estrutura de dados, n˜ao existe uma aresta que

conecte os v´ertices u e v no n´ıvel l > i. Considere-se T

= (V

, E



) e T

= (V

, E



)

como as ´arvores desconectadas pela remo¸c˜ao da aresta (u, v), assumindo-se |V

| ≤

| sem perda de generalidade. Deve-se notar que T = (V, E



∪ {(u, v)} ∪ E



) era

uma ´arvore no n´ıvel i com pelo menos o dobro de v´ertices de T

e que, por (i),

| ≤ n/2

i+1

. Desta forma, preservando-se os invariantes (i) e (ii), as arestas de

podem ter seu n´ıvel aumentado em uma unidade, ou seja, o conjunto E

pode ser

movido para o conjunto de ´arvores de F

i+1

. Agora, o algoritmo deve realizar uma

busca no n´ıvel i, dentre cada uma das arestas incidentes a v´ertices de T

, at´e que

(a) uma aresta de reposi¸c˜ao seja encontrada ou (b) todas as arestas do n´ıvel i sejam

analisadas. Para isso, seja (x, y) a aresta a ser analisada: se essa aresta conecta

as ´arvores desconectadas pela remo¸c˜ao de (u, v) ent˜ao a busca ´e suspensa. Se, por

outro lado, essa aresta n˜ao conecta T

a T

, isso signiﬁca que ambos os v´ertices x e

y pertencem `a mesma ´arvore – especiﬁcamente T

ou T

. O pre¸co da an´alise dessa

aresta ´e pago atrav´es do incremento, em uma unidade, de seu n´ıvel. Por ﬁm, caso n˜ao

existam mais arestas a serem consideradas e o n´ıvel analisado ´e i > 0, a busca deve

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 30

ser realizada em um n´ıvel abaixo, atrav´es da chamada recursiva Replace(u, v, i−1).

Em caso contr´ario, a remo¸c˜ao da aresta (u, v) deixa desconectadas as ´arvores T

Embora de simples descri¸c˜ao, as opera¸c˜oes acima necessitam de estruturas de dados

mais elaboradas para que atinjam a complexidade anunciada. Essa complexidade ser´a

analisada mais adiante. Para cada n´ıvel i, ´e necess´aria a manuten¸c˜ao da ﬂoresta geradora

e das arestas em i n˜ao pertencentes a F

. Para um dado v´ertice v e uma ﬂoresta

geradora F

, existe a necessidade das seguintes opera¸c˜oes:

• identiﬁcar a ´arvore T

∈ F

;

• obter o tamanho de T

;

• encontrar uma aresta de T

no n´ıvel i, se houver;

• encontrar uma aresta do n´ıvel i incidente a T

, se houver; e

• remover e inserir uma aresta no n´ıvel i, seja em F

ou n˜ao.

Todas as opera¸c˜oes acima podem ser executadas pela estrutura de dados ET-trees, de

Henzinger e King [27]. Al´em de ser uma representa¸c˜ao eﬁciente para ´arvores dinˆamicas,

seu rebalanceamento ap´os opera¸c˜oes de inser¸c˜ao e remo¸c˜ao de arestas pode ser realizado

em O(log n). Assim, a cada n´ıvel i ´e associada uma estrutura de dados ET-trees para

representar as arestas de F

. Cada n´o v dessa estrutura deve armazenar informa¸c˜oes sobre

a existˆencia de arestas incidentes a v que n˜ao fazem parte de F

mas est˜ao no n´ıvel i. O

Teorema 3.8 apresenta a complexidade das opera¸c˜oes de atualiza¸c˜ao da estrutura acima.

Teorema 3.8 [30] Dado um grafo G com m arestas e n v´ertices, existe um algoritmo

determin´ıstico totalmente dinˆamico que responde consultas sobre conectividade em tempo

O(log n/ log log n) no pior caso, e que atualiza a ﬂoresta geradora de G em tempo amor-

tizado de O(log

n) para cada opera¸c˜ao de inser¸c˜ao ou remo¸c˜ao de aresta.

Duas altera¸c˜oes fazem com que o algoritmo acima suporte tamb´em atualiza¸c˜oes de

ﬂorestas geradoras m´ınimas. A primeira delas ´e que a ﬂoresta geradora inicial deve ser

m´ınima. A segunda, e mais importante, se encontra na fun¸c˜ao Replace(u, v, i): as arestas

incidentes a T

devem ser analisadas em ordem crescente de custo. Para que isso funcione,

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 31

os custos das arestas devem ser distintos. A corretude do algoritmo pode ser provada

atrav´es da manuten¸c˜ao dos invariantes (i) e (ii), junto com o seguinte invariante:

(iii) Se a aresta (u, v) possui o maior custo dentre as arestas do ciclo C, ela tamb´em

possui o menor n´ıvel l dentre as arestas pertencentes a C.

Este algoritmo tamb´em possui complexidade de O(m log n

), que amortizado sob uma

seq

uencia de Ω(m) opera¸c˜oes resulta na complexidade de O(log

n) (c.f. Teorema 7.3 de

Holm et al. [30]). Entretanto, opera¸c˜oes de inser¸c˜ao de arestas deixam de ser suportadas.

Desta forma, de acordo com a t´ecnica apresentada em [26], adicionando-se log n estruturas

semi-dinˆamicas para remo¸c˜ao, uma opera¸c˜ao de inser¸c˜ao ou remo¸c˜ao de aresta pode ser

executada em O(log

n) [30].

Concluindo esta se¸c˜ao, a Tabela 3.2.4 sumariza a evolu¸c˜ao dos algoritmos aqui apre-

sentados, enfatizando suas complexidades [30].

Os problemas de atualiza¸c˜ao de AGMs devido a altera¸c˜oes em custos de arestas n˜ao pos-

suem algoritmos especiﬁcamente desenvolvidos. Isso porque os algoritmos para inser¸c˜ao

e remo¸c˜ao de arestas podem ser usados para esse ﬁm com a mesma complexidade te´orica.

Desta forma, considere um algoritmo para inser¸c˜ao e remo¸c˜ao de arestas com com-

plexidade O(f(n)) para manter a AGM T . Se, ap´os uma altera¸c˜ao no custo da aresta

(x, y), essa aresta for primeiro removida e ent˜ao inserida com seu novo custo, a complexi-

dade dessa tarefa passa a ser de O(2f(n)) = O(f(n)). Assim, todos os algoritmos acima

apresentados tamb´em podem ser aplicados para o caso de altera¸c˜oes nos custos de arestas.

Contudo, para casos onde o desempenho ´e mandat´orio, como por exemplo em buscas

locais, usar duas opera¸c˜oes (remo¸c˜ao seguida de inser¸c˜ao) para atualizar uma AGM ap´os

uma mudan¸ca de custo pode resultar em uma tarefa cara. Al´em disso, todas as estruturas

de dados e algoritmos at´e ent˜ao estudados introduzem camadas complexas de proces-

samento e armazenamento, resultando em tempos constantes bastante elevados. Essas

constantes, embora n˜ao sejam exibidas pela an´alise assint´otica, podem ser relevantes no

desempenho dos algoritmos.

3.2

Arvores Geradoras M´ınimas em Grafos Dinˆamicos: Algoritmos e Complexidade 32

Tabela 3.1: Evolu¸c˜ao dos algoritmos para grafos dinˆamicos. Tempos com * signiﬁcam complexidade esperada (algoritmos randˆomicos).

A nota¸c˜ao

O(f(n)) indica complexidades polilogar´ıtmicas omitidas, em fun¸c˜ao de f(n), ou seja, esta complexidade corresponde a O(f(n)·

polylog(n)). Representa-se por ∆ o maior grau de um v´ertice pertencente ao grafo. Um grafo ´e biconexo (resp. conectado por duas

arestas) se e somente se a remo¸c˜ao de qualquer v´ertice (resp. aresta) n˜ao resulta na desconex˜ao desse grafo.

Referˆencia Conectividade FGM Conectividade (2 arestas) Biconectividade

Frederickson [17] O(m

1/2

) O(m

1/2

) - -

Frederickson [18] - - O(m

1/2

) -

Eppstein et al. [16] O(n

1/2

) O(n

1/2

) O(n

1/2

) -

Rauch [38] - - - O(m

2/3

)

Rauch [39] - - - O(m

1/2

)

Henzinger e King [25] O(log

n)∗ - O(log

n)∗

O(∆)∗

Henzinger e Poutr´e [28] - - -

O(n

1/2

)

Henzinger e Thorup [29] O(log

n)∗ - - -

Henzinger e King [26]

O(n

1/3

)

O(n

1/3

) - -

Holm et al. [30, 31] O(log

n) O(log

3.3 An´alises Experimentais em AGMs Dinˆamicas 33

Dois trabalhos procuram conduzir avalia¸c˜oes experimentais de algoritmos para ´arvores ge-

radoras m´ınimas em grafos dinˆamicos. O primeiro deles foi proposto por Amato et al. [4] e

inclui implementa¸c˜oes de clusteriza¸c˜ao, ´arvores topol´ogicas, ´arvores topol´ogicas bidimen-

sionais, esparsiﬁca¸c˜ao simples sobre clusteriza¸c˜ao e um algoritmo ingˆenuo, parcialmente

dinˆamico. O segundo trabalho ´e de autoria de Cattaneo et al. [10] e complementa [4],

introduzindo implementa¸c˜oes do algoritmo polilogar´ıtmico de Holm et al. [30, 31] e de um

algoritmo totalmente dinˆamico mais simples e de complexidade elevada.

Os algoritmos implementados por Amato et al. [4] s˜ao apresentados abaixo e resumidos

na Tabela 3.3.

•

Arvores topol´ogicas: esses algoritmos foram propostos por Frederickson [17, 18]

e s˜ao baseados em dois esquemas diferentes de particionamento dos v´ertices, um

proposto em [17] e outro proposto em [18]. Ainda s˜ao propostas altera¸c˜oes nos

algoritmos de Frederickson a ﬁm de utilizar um esquema de parti¸c˜ao mais simples

que os demais, al´em de aplicar atualiza¸c˜oes pregui¸cosas (lazy updates), onde um

novo n´o n˜ao ´e instantaneamente adicionado na ´arvore topol´ogica quando necess´ario,

evitando assim que essa adi¸c˜ao seja seguida pela remo¸c˜ao do mesmo.

• Esparsiﬁca¸c˜ao no topo da clusteriza¸c˜ao: os dois algoritmos implementados

utilizam a t´ecnica de esparsiﬁca¸c˜ao simples, garantindo assim a complexidade de

O(f(n, O(n)) log (m/n )) para um algoritmo com tempo f(n, m). Os certiﬁcados

adotados foram as pr´oprias AGMs dos grafos esparsos gerados pelo particionamento.

• Algoritmo ingˆenuo: o algoritmo ingˆenuo implementado ´e parcialmente dinˆamico.

As arestas do grafo s˜ao mantidas em uma ﬁla de prioridades, enquanto as arestas da

AGM s˜ao armazenadas em ST-trees. Assim, quando uma aresta ´e inserida no grafo,

basta consultar a ´arvore dinˆamica sobre a maior aresta no ciclo para determinar se

a aresta inserida deve ou n˜ao entrar na AGM. Quando uma aresta ´e removida e

pertence `a AGM, o algoritmo de Kruskal [33] ´e aplicado sobre a ﬁla de prioridades.

Dentre os seis algoritmos implementados a partir dos trabalhos de Frederickson,

FredI-85 obteve os melhores tempos computacionais. Desta forma, a an´alise experimen-

tal avaliou, al´em deste, os seguintes algoritmos: FredI-Mod, Spars(I-85), Spars(I-Mod)

e Ad-hoc. A metodologia proposta dividiu os experimentos em duas classes, a citar: classe

de experimentos aleat´orios e classe de experimentos estruturados.

3.3 An´alises Experimentais em AGMs Dinˆamicas 34

Tabela 3.2: Algoritmos implementados por Amato et al. [4].

Algoritmo Estrutura de dados Complexidade

FredI-85 Clusteriza¸c˜ao O(m

2/3

)

FredII-85

Arvores topol´ogicas O((m log m)

1/2

)

FredIII-85

Arvores topol´ogicas bidimensionais O(m

1/2

)

FredI-91 Clusteriza¸c˜ao O(m

2/3

)

FredII-91

Arvores topol´ogicas O((m log m)

1/2

)

FredIII-91

Arvores topol´ogicas bidimensionais O(m

1/2

)

FredI-Mod Clusteriza¸c˜ao O(m

2/3

)

Spars(I-85) Esparsiﬁca¸c˜ao sobre clusteriza¸c˜ao O(n

2/3

)

Spars(I-Mod) Esparsiﬁca¸c˜ao sobre clusteriza¸c˜ao O(n

2/3

)

Ad-hoc ST-trees e ﬁla de prioridades O(m log n)

Para a primeira classe de experimentos, foram gerados grafos aleat´orios com n v´er-

tices e m arestas, com custos escolhidos aleatoriamente. As seq

uˆencias de atualiza¸c˜oes

do grafo tamb´em foram aleat´orias, compostas por 2000 atualiza¸c˜oes (1000 inser¸c˜oes e

1000 remo¸c˜oes de arestas). Foram feitas execu¸c˜oes utilizando dez sementes diferentes.

Resultados para grafos com 200 v´ertices e de 200 a 10000 arestas e para grafos com 700

v´ertices e de 700 a 149000 arestas foram apresentados, para os quais o desempenho do

algoritmo Ad-hoc foi superior aos outros algoritmos. A ordem dos resultados – Ad-hoc,

FredI-Mod, FredI-85, Spars(I-Mod) e Spars(I-85) – pode ser explicada pela teoria dos

grafos: o algoritmo Ad-hoc possui excelente desempenho em todos os casos com exce¸c˜ao

da remo¸c˜ao de arestas da AGM. Como isso ocorre com probabilidade de n/m em grafos

aleat´orios, o resultado pr´atico foi compat´ıvel com a teoria.

Por outro lado, os experimentos estruturados foram projetados para for¸car a ocorrˆen-

cia de seq

uˆencias caras de atualiza¸c˜oes, formadas exclusivamente por remo¸c˜oes de arestas

da AGM, que ´e o pior caso para o problema de manuten¸c˜ao de ´arvores geradoras m´ınimas

em grafos dinˆamicos (todos os outros casos podem ser tratados em O(log n)). Neste caso,

o algoritmo Ad-hoc foi prejudicado pelas seq

uˆencias de atualiza¸c˜oes e seu tempo n˜ao foi

contabilizado nos experimentos. O algoritmo Spars(I-Mod) teve a melhor performance,

seguido por FredI-Mod, Spars(I-85) e FredI-85.

O trabalho de Cattaneo et al. [10] complementa os estudos realizados em [4] ao intro-

duzir o algoritmo de Holm et al. [31]. Os algoritmos analisados foram:

• Spars(I-Mod): este ´e o mesmo algoritmo que obteve o melhor desempenho na

an´alise experimental de Amato et al. [4].

3.3 An´alises Experimentais em AGMs Dinˆamicas 35

• ST: para o grafo G = (V, E) e AGM T = (V, E



), este algoritmo armazena as arestas

do sub conjunto E − E



ordenadas sob uma ´arvore balanceada (AVL), garantindo

O(log n) em opera¸c˜oes tanto de inser¸c˜ao quanto de remo¸c˜ao de arestas que n˜ao fazem

parte da AGM. Esta ´arvore balanceada ´e usada em conjunto com uma estrutura

ST-trees, garantindo tamb´em complexidade logar´ıtmica em inser¸c˜oes de arestas. A

remo¸c˜ao de arestas da AGM ´e feita atrav´es de um percurso ordenado na ´arvore,

onde para cada aresta visitada ´e feita uma pergunta sobre conectividade da AGM,

atrav´es das ST-trees. Esta opera¸c˜ao tem complexidade O(m log n), j´a que, no pior

caso, s˜ao visitadas O(m) arestas, com complexidade O(log n) para cada chamada `a

fun¸c˜ao Connected das ST-trees.

• ET+ST: foi constatado que a opera¸c˜ao Connected da estrutura ST-trees ´e muito lenta

quando comparada `a da estrutura ET-trees. Assim sendo, este algoritmo mant´em

duas AGMs: a primeira, sobre as ET-trees propriamente ditas, executa perguntas

sobre conectividade no algoritmo de remo¸c˜ao de arestas da AGM. A segunda, sobre

as ST-trees, obt´em a aresta de maior custo em um caminho para o algoritmo de

inser¸c˜ao de arestas (j´a que as ET-trees n˜ao suportam opera¸c˜oes sobre caminhos).

• HDT: implementa¸c˜ao do algoritmo polilogar´ıtmico de Holm et al. [30, 31].

Os algoritmos acima foram submetidos a quatro classes de experimentos, que procu-

raram analisar os diversos problemas envolvidos na atualiza¸c˜ao dinˆamica de uma AGM.

Para o primeiro experimento foram consideradas entradas aleat´orias de 2000 v´ertices

e 2000 a 95000 arestas, com 20000 atualiza¸c˜oes tamb´em aleat´orias – 10000 inser¸c˜oes e

10000 remo¸c˜oes. Os algoritmos ST e ET+ST foram consideravelmente mais r´apidos que os

outros dois. O algoritmo Spars(I-Mod) (resp. HDT) obteve tempos de CPU em torno

de quatorze vezes (resp. trˆes vezes) maiores que os dois algoritmos mais r´apidos (ST e

ET+ST).

Por ﬁm, foi realizado um experimento onde aproximadamente 90% das inser¸c˜oes e

remo¸c˜oes de arestas resultariam em altera¸c˜oes na AGM. Nesses testes os tempos dos al-

goritmos aumentaram cerca de dez vezes, resultado das freq

uentes altera¸c˜oes na estrutura

da ´arvore geradora m´ınima. O ´unico algoritmo que apresentou comportamento diferente

sob essa situa¸c˜ao foi ST, pois remo¸c˜oes de arestas da AGM resultam em seguidas consul-

tas de conectividade na busca por uma aresta substituta `aquela removida, penalizando as

ST-trees devido `a complexidade de sua estrutura quando comparada com a estrutura das

ET-trees.

3.4 An´alise dos Algoritmos para Atualiza¸c˜ao de

Arvores Geradoras M´ınimas 36

O segundo experimento foi realizado sobre trˆes conjuntos de instˆancias semi-aleat´orias.

Na primeira delas, onde foram utilizadas pequenas componentes conexas em um grafo com

2000 v´ertices e apenas 1000 arestas, os algoritmos ST, ET+ST e HDT apresentaram ´otimo

desempenho se comparados com o algoritmo Spars(I-Mod), pois possuem custos cons-

tantes muito menores que o ´ultimo algoritmo. Outros dois experimentos foram realizados

para 2000 e 4000 arestas, tamb´em resultando em grafos esparsos mas com componentes

conexas maiores. Nessa situa¸c˜ao, os algoritmos ET+ST e Spars(I-Mod) apresentaram bom

desempenho perante os outros dois algoritmos. O desempenho de ST ´e muito degradado

quando utilizado em grafos assim instanciados.

Tamb´em foram propostas instˆancias denominadas k-Clique, onde s˜ao geradas k cliques

de tamanho c cada, totalizando n = kc v´ertices. Estas cliques s˜ao conectadas entre si

atrav´es de 2k arestas inter-clique aleatoriamente geradas, o que resulta em uma AGM

fortemente conectada por arestas intra-cliques, por´em fracamente conectada por arestas

inter-cliques, resultando no dif´ıcil tratamento de remo¸c˜oes dessas arestas. Foi reportado

que os algoritmos ET+ST e ST n˜ao foram competitivos para esta classe de grafos e, portanto,

n˜ao foram testados. O algoritmo HDT ´e o mais r´apido desta classe, pois sua estrutura em

camadas consegue se adaptar `a estrutura tamb´em de camadas formada pelas cliques.

O ´ultimo experimento deste trabalho ´e realizado sob grafos especiﬁcamente criados

para simular casos ruins para o algoritmo HDT. Tais casos podem ser formulados atrav´es

de sucessivas mudan¸cas de n´ıvel para as arestas do grafo, que ent˜ao, ao atingir o n´ıvel

mais alto da estrutura, s˜ao removidas. Nesse experimento o algoritmo Spars(I-Mod) foi

mais r´apido, embora n˜ao mais que duas vezes, que o algoritmo HDT.

O trabalho de Zaroliagis [48] analisa os dois experimentos acima.

At´e ent˜ao, foram apresentadas estruturas de dados para armazenar e tratar ´arvores su-

jeitas a altera¸c˜oes dinˆamicas. Tamb´em foi apresentada a problem´atica introduzida por

altera¸c˜oes estruturais no grafo a partir do qual uma ´arvore geradora m´ınima foi calculada.

Por ﬁm, algoritmos para o problema de atualiza¸c˜ao de ´arvores geradoras m´ınimas foram

ilustrados e analisados experimentalmente.

Contudo, embora existam duas estruturas de dados (ET-trees e ST-trees) para ´arvores

dinˆamicas que s˜ao utilizadas em praticamente todos os algoritmos para atualiza¸c˜ao de

3.5 Resumo do Cap´ıtulo 37

´arvores geradoras m´ınimas em grafos dinˆamicos, n˜ao existe na literatura um estudo que

compare essas estruturas com outras de implementa¸c˜ao direta e, por conseq

uˆencia, mais

simples.

Assim, foi analisado experimentalmente as estruturas de dados mais comuns em al-

goritmos dinˆamicos para ´arvores geradoras m´ınimas. Ainda, como resultado de estudos

preliminares, foi necess´ario criar-se uma nova estrutura de dados para ´arvores dinˆamicas,

com a fun¸c˜ao de responder rapidamente a quest˜oes sobre conectividade entre dois n´os.

Esta estrutura, bem como a an´alise experimental das implementa¸c˜oes mais importantes

de estruturas de dados para ´arvores dinˆamicas, s˜ao apresentadas no Cap´ıtulo 4.

Por outro lado, quanto aos algoritmos para atualiza¸c˜ao de AGMs ap´os inser¸c˜oes e

remo¸c˜oes de arestas, an´alises experimentais mostraram que o algoritmo HDT n˜ao possui

desempenho favor´avel na pr´atica, ainda que sua an´alise te´orica aﬁrme o contr´ario. Seu

fraco desempenho ´e resultado direto de sua dif´ıcil implementa¸c˜ao, onde s˜ao necess´arias

camadas de estruturas que degradam sensivelmente seu comportamento na pr´atica.

Ainda que suas implementa¸c˜oes fossem eﬁcientes, utilizar algoritmos para atualiza¸c˜ao

de AGMs ap´os inser¸c˜oes e remo¸c˜oes de arestas em problemas de modiﬁca¸c˜oes em custos de

arestas resultaria em desempenho ainda mais prejudicado, j´a que cada atualiza¸c˜ao traria

a necessidade da execu¸c˜ao de duas op era¸c˜oes: uma remo ¸c˜ao seguida de uma inser¸c˜ao.

Deste modo, observou-se a necessidade de novos algoritmos que sejam, ao mesmo

tempo, r´apidos e de simples implementa¸c˜ao, e ainda espec´ıﬁcos para altera¸c˜oes dinˆamicas

nos custos de arestas. Para isso, um novo algoritmo ser´a proposto e analisado, teorica e

experimentalmente, no Cap´ıtulo 5 desta disserta¸c˜ao.

Este cap´ıtulo apresentou os principais t´opicos que cobrem o estudo de algoritmos e estru-

turas de dados para atualiza¸c˜ao de ´arvores geradoras m´ınimas em grafos dinˆamicos. Foi

discutida a problem´atica causada por altera¸c˜oes dinˆamicas no grafo, e em seguida foram

apresentados os algoritmos e estruturas de dados propostos pela literatura, bem com suas

an´alises experimentais.

Por ﬁm, foram discutidas as principais carˆencias da literatura no que diz respeito a

estruturas de dados para ´arvores dinˆamicas e a algoritmos eﬁcientes para atualiza¸c˜ao de

´arvores geradoras m´ınimas em grafos sujeitos a altera¸c˜oes dinˆamicas em custos de arestas.

3.5 Resumo do Cap´ıtulo 38

Conseq

uentemente, esta disserta¸c˜ao traz, nos Cap´ıtulos 4 e 5, alternativas que procuram

resolver, respectivamente, ambos os problemas.

Este cap´ıtulo apresenta a estrutura de dados DRD-trees (doubly-linked reversed dyna-

mic trees), que ´e uma contribui¸c˜ao desta disserta¸c˜ao. Essa estrutura de dados foi proje-

tada para responder quest˜oes espec´ıﬁcas sobre conectividade em tempo constante, quando

amortizado sobre o m´ınimo de n opera¸c˜oes.

As ´arvores dinˆamicas s˜ao essenciais para a manuten¸c˜ao de ´arvores geradoras m´ınimas

sujeitas a altera¸c˜oes estruturais freq

uentes, o que ocorre em problemas que envolvem gra-

fos dinˆamicos. Embora todas as implementa¸c˜oes eﬁcientes de ´arvores dinˆamicas possam

responder quest˜oes sobre conectividade em tempo logar´ıtmico, foi observada experimen-

talmente uma not´avel sobrecarga nessa opera¸c˜ao. Visando melhorar os tempos compu-

tacionais dessa opera¸c˜ao, prop˜oe-se uma nova estrutura para ´arvores dinˆamicas, baseada

nas RD-trees, denominada DRD-trees – ´arvores dinˆamicas duplamente encadeadas.

As DRD-trees ampliam as RD-trees ao estender o conceito de um n´o v ∈ V . Na se-

gunda estrutura o n´o v armazena apenas as informa¸c˜oes π[v] (seu pai na ´arvore dinˆamica)

e ω[v] (custo do arco (v, π[v])). Na primeira estrutura, o n´o v passa a armazenar, al´em

desses dois dados, a lista S(v) = {x

, x

, . . .} ∀ x

∈ V tal que π[x

] = v. Assim, s˜ao

representados tamb´em os ﬁlhos de v, justiﬁcando a nomenclatura de ´arvore duplamente

encadeada.

Armazenar os ﬁlhos de um n´o permite a realiza¸c˜ao de buscas em profundidade a

partir de um dado n´o v ∈ V , o que pode ser utilizado para a realiza¸c˜ao de consultas

4.1 DRD-trees: Uma Proposta de

Arvores Dinˆamicas 40

r´apidas, em tempo constante amortizado, sobre conectividade entre dois n´os (Se¸c˜ao 4.2).

Na Figura 4.1 (a), uma AGM ´e mapeada atrav´es de DRD-trees (foi omitida a lista de

ﬁlhos de cada n´o); em (b) a aresta (b, f) ´e removida da AGM; e em (c) ´e mostrado o

resultado da busca em largura realizada a partir do n´o f, abrangendo, al´em de f, os n´os

d e g (ﬁlhos de f na estrutura de dados).

(a) (b) (c)

Figura 4.1: AGM representada atrav´es de DRD-trees.

As opera¸c˜oes necess´arias para ´arvores dinˆamicas [41] s˜ao assim implementadas nas

DRD-trees aqui propostas:

• Link(u, v, c): ´e implementada de maneira idˆentica `as RD-trees, com exce¸c˜ao da

opera¸c˜ao S(u) ← S(u) ∪ {v}, que adiciona o v´ertice v `a lista dos ﬁlhos de u. Todas

as opera¸c˜oes tem tempo constante.

• Cut(u, v): al´em da atualiza¸c˜ao de π[u], deve-se remover o n´o u de S(v). Embora

a atualiza¸c˜ao de π seja constante, remover o n´o u da lista S(v) tem complexidade

linear em n no pior caso.

• Root(v): esta opera¸c˜ao n˜ao ´e diferente das RD-trees; basta subir na ´arvore at´e que

a raiz da mesma seja encontrada. Sua complexidade ´e O(n) no pior caso.

• Cost(u, v): retorna o custo armazenado em ω[u] (resp. ω[v]) se π[u] = v (resp.

π[v] = u), com complexidade O(1). Caso nenhuma dessas condi¸c˜oes seja satisfeita,

esta fun¸c˜ao retorna um valor especial representando a ausˆencia da aresta (u, v).

• Find_min(v): sobe na ´arvore at´e encontrar sua raiz, armazenando a aresta de menor

custo durante a subida. A complexidade deste m´etodo ´e O(n).

• Update(v, c): muito parecido com o m´etodo Find_min(v), onde na subida ´e adici-

onado o valor c ao custo de cada aresta percorrida.

4.2 Consultas de Conectividade em Tempo Constante 41

• Evert(v): implementado p elo Algoritmo 5.

Algoritmo 5 Evert(v) para estruturas de dados DRD-trees

Entrada: O novo n´o raiz v e a ´arvore T = (V, E



1: p ← π[v];

2: se p = 0 ent˜ao

3: retorne 0;

4: ﬁm se

5: Evert(p);

6: π[p] ← v;

7: π[v] ← 0;

8: S(p) ← S(p) − {v};

9: S(v) ← S(v) ∪ {p};

10: ω[p] ← ω[v];

A execu¸c˜ao do Algoritmo 5 tamb´em ´e recursiva. O caso base da recurs˜ao ocorre

quando um n´o raiz p ´e atingido, para ent˜ao as linhas 6 − 10 transformarem o n´o v na nova

raiz da ´arvore. O n´o raiz p ´e ent˜ao adicionado na lista dos ﬁlhos de v e, ao ﬁm da pilha

de recurs˜ao, o n´o v da primeira chamada recursiva ´e transformado em n´o raiz. Deve-se

notar que a opera¸c˜ao da linha 8 pode ter custo linear.

A complexidade do Algoritmo 5 ´e de O(n) no pior caso. Se a ´arvore transformada ´e

linear, s˜ao executadas O(n) chamadas de custo constante – nesse caso a busca na lista de

ﬁlhos para ´arvores lineares ´e executada em tempo constante.

O fato das DRD-trees serem implementadas sobre ´arvores duplamente encadeadas pode

ser utilizado no desenvolvimento de um algoritmo para avalia¸c˜ao da fun¸c˜ao Connected

com complexidade O(1), quando amortizado sobre n opera¸c˜oes. Se uma opera¸c˜ao de busca

em largura ´e previamente executada, com custo O(n), pode-se construir uma tabela de

consultas sob a forma de um vetor com n posi¸c˜oes. A necessidade da busca em largura

ser´a ilustrada de maneira top-down, partindo da necessidade de eﬁciˆencia para consultas

de conectividade, conforme foi salientado no trabalho experimental de Cattaneo et al. [10].

As consultas Connected(x, y) s˜ao executadas todas as vezes que a AGM T = (V, E



)

´e desconectada pela remo¸c˜ao de uma aresta. Essas consultas s˜ao feitas sobre as arestas

(x, y) /∈ E



e demandam um grande esfor¸co computacional, j´a que cada uma custa O(log n)

em implementa¸c˜oes eﬁcientes de ´arvores dinˆamicas. A intui¸c˜ao da busca em largura ´e a

seguinte: considere as ´arvores T

e T

resultantes da remo ¸c˜ao da aresta (u, v) de T . Se os

4.3 Resumo do Cap´ıtulo 42

v´ertices pertencentes a T

s˜ao mapeados em um vetor de tamanho n, ´e poss´ıvel veriﬁcar

se a aresta arbitr´aria (x, y) conecta as ´arvores T

e T

em O(1) atrav´es de duas consultas

a esse vetor. Caso o v´ertice x esteja mapeado no vetor e o v´ertice y n˜ao (ou vice-versa),

(x, y) certamente reconecta a ´arvore geradora m´ınima T .

A an´alise amortizada ´e aqui apresentada atrav´es da t´ecnica de contagem [12]. Se, ap´os

a opera¸c˜ao linear de busca em largura, n opera¸c˜oes de tempo constante forem executadas,

a complexidade amortizada constante dessas O(n) opera¸c˜oes (somando-se a´ı a opera¸c˜ao

de busca em largura) pode ser provada pela Equa¸c˜ao 4.1.

O(n) + n · O(1)

O(n)

= O(1). (4.1)

Na Equa¸c˜ao 4.1, O(n) ´e o custo da busca em largura e da aloca¸c˜ao das n posi¸c˜oes do

vetor de consultas e O (1) ´e o custo de veriﬁcar as posi¸c˜oes x e y do array para saber se x

ou y pertence `a ´arvore T

Neste cap´ıtulo foi proposta uma estrutura de dados capaz de executar consultas sobre

conectividade em tempo constante, se amortizadas em seq

uˆencias de O(n) consultas. A

estrutura apresenta desempenho linear para opera¸c˜oes relacionadas a caminhos e para

a opera¸c˜ao Cut. Para todas as outras opera¸c˜oes s˜ao oferecidos algoritmos com tempo

constante.

Desta forma, a estrutura de dados DRD-trees pode ser utilizada em algoritmos para

manuten¸c˜ao de ´arvores geradoras em grafos dinˆamicos. O Cap´ıtulo 5 prop˜oe um algoritmo

de complexidade O(m) para este problema, usando para isso a estrutura DRD-trees.

Neste cap´ıtulo ´e apresentado um algoritmo on-line totalmente dinˆamico para o problema

de atualiza¸c˜ao de ´arvores geradoras m´ınimas em grafos dinˆamicos. Dois casos s˜ao tratados

separadamente: o caso de decrementos nos custos de arestas ´e considerado na Se¸c˜ao 5.2 e

o caso de incrementos nos custos de arestas ´e ent˜ao considerado na Se¸c˜ao 5.3.

Os algoritmos apresentados nas Se¸c˜oes 5.2 e 5.3 s˜ao coordenados por um algoritmo centra-

lizado respons´avel tamb´em pelo armazenamento do grafo G = (V, E) sujeito a altera¸c˜oes

dinˆamicas. Esse algoritmo deve permitir acesso a qualquer aresta do grafo em O(1) e que

uma aresta seja atualizada atrav´es de incrementos ou decrementos em seu custo. Como

requisito para os algoritmos que ser˜ao apresentados, tais arestas devem ser armazenadas

em uma lista duplamente encadeada e mantidas em ordem crescente de custo. Assim, a

cada atualiza¸c˜ao no custo de uma aresta, esta deve ser movimentada atrav´es dessa lista

de forma a manter a ordem pr´e-estabelecida.

Para oferecer acesso em tempo constante a qualquer aresta do grafo, foi adotada uma

matriz contendo ponteiros para os n´os da lista duplamente encadeada contendo as arestas

propriamente ditas. Deste modo, a posi¸c˜ao P (i, j) dessa matriz armazena um ponteiro p

para posi¸c˜ao da lista que cont´em a aresta (i, j). Em seguida, essa lista de arestas pode

ser acessada atrav´es da nota¸c˜ao A(p). Como a lista em quest˜ao ´e duplamente encadeada,

as opera¸c˜oes p ← p + 1 e p ← p − 1 retornam ponteiros para o n´o seguinte e anterior a p,

respectivamente.

O funcionamento deste algoritmo centralizado ´e apresentado no Algoritmo 6.

5.1 Estrutura de Dados 44

Algoritmo 6 Atualiza¸c˜ao de ´arvores geradoras m´ınimas ap´os altera¸c˜oes de custos

Entrada: Grafo G = (V, E) e custos w.

1: Construir uma lista duplamente encadeada A contendo as arestas de G;

2: Organizar a lista A em ordem crescente de custos;

3: Construir uma matriz P de ponteiros para os n´os de A;

4: Usar A para construir a AGM T = (V, E



) pelo m´etodo de Kruskal (Algoritmo 1);

5: enquanto existem atualiza¸c˜oes a serem processadas fa¸ca

6: (i, j) ← aresta a ser atualizada;

7: c ← novo custo da aresta (i, j);

8: c



← w(i, j);

9: w(i, j) ← c;

10: p ← P (i, j) + 1;

11: Reordenar a lista A mantendo-a em ordem crescente de custos;

12: f ← P (i, j);

13: se w(i, j) < c



ent˜ao

14: Executar o Algoritmo 7 com os parˆametros T , (i, j) e w;

15: sen˜ao se w(i, j) > c



ent˜ao

16: Executar o Algoritmo 9 com os parˆametros T , (i, j), p, f e w;

17: ﬁm se

18: ﬁm enquanto

O Algoritmo 6 ´e utilizado para manter a lista de arestas ordenada, bem como decidir

sobre qual algoritmo utilizar: incremento ou decremento de custos. Para tanto, este

algoritmo recebe inicialmente um grafo G = (V, E), o qual ´e utilizado para a constru¸c˜ao da

lista duplamente encadeada A. Esta lista ´e ent˜ao ordenada e, para cada n´o da mesma, um

ponteiro ´e criado em uma matriz P com o objetivo de oferecer acesso em tempo constante

para qualquer aresta de A (i.e., quando deseja-se atualizar uma aresta arbitr´aria (i, j),

n˜ao ´e necess´ario percorrer A para localizar essa aresta; pode-se acessar (i, j) diretamente

atrav´es de P (i, j)). Constr´oi-se a AGM inicial T = (V, E



) atrav´es do Algoritmo 1.

O pr´oximo passo ´e executar a seguinte seq

uˆencia enquanto existem atualiza¸c˜oes a

serem processadas (i.e., arestas no grafo para serem atualizadas): a linha 6 recebe uma

aresta (i, j) que ser´a atualizada com o novo valor c para seu custo, que ´e recebido como

entrada na linha 7. Em seguida o custo atual de (i, j) (antes da atualiza¸c˜ao propriamente

dita) ´e armazenado em c



, para ent˜ao, na linha 9, o valor w(i, j) ser alterado para c. Neste

ponto a lista A de arestas pode ter sua ordem violada, o que ´e corrigido pela linha 11, onde

um procedimento de reordena¸c˜ao ´e executado. Este pro cedimento ´e simples e consiste em

deslocar a aresta atualizada para frente (caso seu peso tenha sido incrementado) ou para

tr´as (caso seu peso tenha sido decrementado), at´e que ela seja disposta em uma posi¸c˜ao

onde a lista A ﬁque ordenada novamente. Antes dessa opera¸c˜ao, o algoritmo ainda guarda

em p o ponteiro para o n´o A(P (i, j) + 1), ou seja, a posi¸c˜ao da aresta imediatamente ap´os

5.2 Algoritmo para Decremento no Custo de Arestas 45

(i, j) na lista A (linha 10). Finalmente, a posi¸c˜ao de (i, j) ap´os a reordena¸c˜ao ´e armazenada

em f na linha 12, para ent˜ao se fazer a chamada ao algoritmo que trata o sub-problema

de decremento (linha 14) ou incremento (linha 16) em custos de arestas.

As Se¸c˜oes 5.2 e 5.3 apresentam os algoritmos para incremento e decremento em custos

de arestas, respectivamente.

Resolver o caso de decremento em custos de arestas ´e a parte mais f´acil do problema e

pode ser resolvido por qualquer implementa¸c˜ao de ´arvores dinˆamicas. Basta para isso

armazenar a AGM usando uma dessas ´arvores. Se a aresta decrementada (i, j) n˜ao per-

tence `a AGM, basta veriﬁcar na ´arvore dinˆamica qual ´e a aresta de maior custo no ciclo

induzido pela inser¸c˜ao dessa aresta. Se a aresta (x, y) retornada possuir custo maior, ´e

necess´ario removˆe-la da AGM e ent˜ao inserir (i, j) como aresta substituta. O Algoritmo 7

cont´em a implementa¸c˜ao desta tarefa.

Algoritmo 7 Decremento no custo de uma aresta

Entrada: AGM T = (V, E



) (possivelmente desatualizada), a aresta (i, j) cujo custo foi

decrementado e os custos w.

1: se (i, j) ∈ E



ent˜ao

2: Atualizar o custo de (i, j) em T ;

3: sen˜ao

4: se i = Root(i) ent˜ao

5: Evert(i);

6: ﬁm se

7: (x, y) ← Find_max(j);

8: se w(x, y) > w(i, j) ent˜ao

9: Cut(x, y);

10: Link(i, j, w(i, j));

11: ﬁm se

12: ﬁm se

13: retorne a AGM atualizada T ;

A eﬁciˆencia desta opera¸c˜ao depende totalmente da implementa¸c˜ao de ´arvore dinˆamica

utilizada para armazenamento da ´arvore geradora m´ınima. Em implementa¸c˜oes eﬁcientes

de ´arvores dinˆamicas, sua complexidade de tempo ´e O(log n).

5.3 Algoritmo para Incremento no Custo de Arestas 46

Dada uma AGM T = (V, E



), incrementar o custo de uma aresta arbitr´aria (i, j) ∈ E



´arvore geradora m´ınima ´e certamente o caso mais complexo a ser tratado, j´a que existe

a possibilidade da existˆencia de uma aresta (x, y) tal que w(x, y) < w(i, j). Nesse caso,

deve-se pro curar a aresta (x, y) de menor custo conectando as duas ´arvores disjuntas

resultantes da remo¸c˜ao de (i, j).

A n˜ao-trivialidade desta tarefa ´e assim ilustrada: suponha-se que, na AGM T =

(V, E



), a aresta (i, j) ∈ E



foi incrementada em k unidades. A remo¸c˜ao dessa aresta

deixaria duas componentes desconectadas, a nomear T

= (V

, E



) e T

= (V

, E



), com

V = V

∪ V

e E



= E



∪ {(i, j)} ∪ E



. Se |V

| = n/2, ent˜ao |V

| = n/2. Assim,

poderiam existir n/2 · n/2 arestas a serem analisadas caso o grafo G seja completo,

ou seja, O(n

) arestas [44].

O Algoritmo 8 apresenta um m´etodo simples para atualizar uma ´arvore geradora

m´ınima T = (V, E



) ap´os a aresta (i, j) ter seu custo incrementado. De acordo com o

Algoritmo 6, p ´e um ponteiro que representa a aresta seguinte a (i, j) na lista A antes da

chamada ao algoritmo de reordena¸c˜ao (p = P (i, j) + 1). Ap´os o algoritmo de reordena¸c˜ao

ser executado, ´e ent˜ao atribu´ıda a f a posi¸c˜ao atual da aresta (i, j) em A.

Algoritmo 8 Incremento no custo de uma aresta

Entrada: AGM T = (V, E



) (possivelmente desatualizada), a aresta (i, j) cujo custo foi

incrementado, os ponteiros

para a lista

e os custos

1: Cut(i, j);

2: enquanto p ≤ f fa¸ca

3: (x, y) ← A(p);

4: se Root(x) = Root(y) ent˜ao

5: Link(x, y, w(x, y));

6: retorne a ´arvore geradora m´ınima atualizada T ;

7: ﬁm se

8: p ← p + 1;

9: ﬁm enquanto

De acordo com o Algoritmo 8, a aresta (i, j) ´e removida de E



(conjunto de arestas da

´arvore T = (V, E



) possivelmente desatualizado) atrav´es da opera¸c˜ao Cut(i, j), na linha

1. Em seguida, nas linhas 2-9, inicia-se a opera¸c˜ao de busca pela aresta que ir´a substituir

(i, j) em E



(como p pode chegar at´e o n´o A(f) contendo (i, j), em ´ultimo caso a AGM

permanece inalterada pela reinser¸c˜ao dessa aresta). Para tanto, ´e atribu´ıda a (x, y) a

aresta que encontra-se na posi¸c˜ao p, ou seja, (x, y) ← A(p). Como ser´a provado mais

adiante que a aresta substituta a (i, j) est´a obrigatoriamente entre as posi¸c˜oes p e f da

5.3 Algoritmo para Incremento no Custo de Arestas 47

lista de arestas A, basta realizar uma busca seq

uencial em A, partindo de A(p) e limitada

a A(f). Esta busca dever´a procurar pela aresta de menor custo (x, y) que conecta as

´arvores T

e T

, o que corresponde a procurar pela menor aresta (x, y) tal que o v´ertice x

se encontre em T

(resp. T

) e que o v´ertice y se encontre em T

(resp. T

A linha 3 atribui a (x, y) a primeira aresta candidata a substituir (i, j) em E



. Na linha

4, a estrutura de dados para ´arvores dinˆamicas que armazena T ´e acessada de modo a

responder se (x, y) conecta as duas ´arvores disjuntas T

e T

que resultaram da remo¸c˜ao de

(i, j) na linha 1. Enquanto esta aresta n˜ao for encontrada, as linhas 8 e 3 respectivamente

caminham com o ponteiro p para a pr´oxima aresta da lista A e a atribuem a (x, y),

aresta que ser´a ent˜ao analisada na pr´oxima itera¸c˜ao, at´e que (x, y) satisfa¸ca a condi¸c˜ao de

conectar T

a T

. Nesse ponto, P (x, y) encontra-se ou no intervalo [p, f) (caso em que a

AGM ser´a alterada) ou na posi¸c˜ao f (caso em que a AGM n˜ao mudar´a). A consolida¸c˜ao

dessa busca (atualiza¸c˜ao de T ) ´e realizada nas linhas 5 e 6, com a execu¸c˜ao da opera¸c˜ao

Link(x, y, w(x, y)) e, por ﬁm, com o t´ermino do algoritmo, retornando a AGM atualizada.

Teorema 5.1 O Algoritmo 8 atualiza corretamente a AGM T .

Prova A aresta (i, j) sofreu um incremento de custo. O primeiro passo ´e provar que

a aresta de menor custo (x, y) conectando T

a T

n˜ao pode estar antes da aresta A(p)

na lista ordenada de arestas. Suponha-se que A (k) corresponde `a aresta (x, y) para

qualquer k ∈ {1, . . . , p − 1}. Nesse caso, a AGM antes da atualiza¸c˜ao de (i, j) n˜ao seria

m´ınima, j´a que w(x, y) < w(i, j) (as arestas onde w(x, y) = w(i, j) n˜ao foram inclu´ıdas

na ´arvore por conﬂitarem (i.e., causarem a forma¸c˜ao de ciclos em T ) com outras arestas

que tamb´em se encontram entre as posi¸c˜oes 1 e p − 1 da lista A. Tamb´em ´e necess´ario

provar que (x, y) n˜ao pode estar depois de A(f ). Suponha-se que A(k) seja a aresta (x, y)

para algum k ∈ {f + 1, . . . , m}. Nesse caso, a nova AGM n˜ao poderia ser ´otima, j´a

que w(i, j) < w(x, y) (exceto para os casos onde w(i, j) = w(x, y), aos quais o pr´oximo

par´agrafo cont´em uma restri¸c˜ao).

Tamb´em ´e necess´ario provar que o algoritmo acima mant´em a pol´ıtica do algoritmo de

Kruskal [33], onde a primeira aresta em ordem de custo que conecte duas sub-´arvores

disjuntas deve ser escolhida para fazer parte da AGM T . Esse caso ´e de suma importˆancia

em grafos onde existem arestas de mesmo custo. Para isso, quando uma aresta tem seu

custo incrementado, o m´etodo para reordena¸c˜ao de arestas n˜ao precisa se preocupar em

posicionar a aresta dentre aquelas com mesmo custo, j´a que o Algoritmo 8 far´a a sele¸c˜ao

baseada no m´etodo de Kruskal. Contudo, se a aresta (i, j) tem seu custo decrementado,

5.3 Algoritmo para Incremento no Custo de Arestas 48

deve-se atentar ao procedimento adotado pelo Algoritmo 7, que somente modiﬁca a AGM

quando w(x, y) > w(i, j) (ou seja, quando h´a empates a AGM n˜ao ´e alterada). Com esse

procedimento, o m´etodo de reordena¸c˜ao deve deslocar a aresta (i, j) para a esquerda at´e

que encontre a primeira aresta com custo igual ao dela. Desta forma, ´e garantido que,

se (x, y) tiver seu custo incrementado futuramente, (i, j) seria uma aresta substituta no

Algoritmo 8.

Teorema 5.2 O Algoritmo 8 atualiza uma ´arvore geradora m´ınima em tempo O(m log n)

(resp. O(mn)) se T for representada atrav´es de ST-trees (resp. RD-trees).

Prova Note que a lista A j´a se encontra ordenada. Desta forma, o pior caso ocorre quando

a aresta (i, j) ´e deslocada da primeira at´e a ´ultima posi¸c˜ao de A e ainda n˜ao existe uma

aresta substituta. Neste caso, cada chamada ao m´etodo Connected tem complexidade

O(log n) (resp. O(n)), resultando no tempo total de O( m log n) (resp. O(mn)) se a

´arvore for representada por ST-trees (resp. RD-trees).

Os algoritmos acima s˜ao simples de implementar e possuem baixas constantes de

implementa¸c˜ao. Experimentos preliminares comprovaram sua viabilidade quando compa-

rados aos m´etodos est´aticos de Kruskal [33] e Prim [37], mesmo todos eles possuindo a

mesma complexidade assint´otica. Entretanto, foi observado que as chamadas de conec-

tividade dominaram a utiliza¸c˜ao de tempo dentro do algoritmo, al´em do fato que cortes

e liga¸c˜oes desnecess´arias s˜ao executados toda vez que uma aresta ´e incrementada e n˜ao

existem arestas substitutas no intervalo [p, f) (ou seja, a AGM permaneceu inalterada

ap´os a opera¸c˜ao de incremento).

Tendo em mente as duas diﬁculdades citadas acima, ´e proposto o Algoritmo 9 que

utiliza as DRD-trees propostas no Cap´ıtulo 4. A utiliza¸c˜ao dessa estrutura por si s´o j´a

elimina a necessidade de cortes e liga¸c˜oes desnecess´arias, j´a que a busca em profundi-

dade n˜ao requer que as ´arvores sejam desconectadas, ao contr´ario das outras estruturas

dinˆamicas onde as ra´ızes de T

e T

s˜ao pesquisadas a cada aresta veriﬁcada.

Nesse algoritmo, as principais altera¸c˜oes com rela¸c˜ao ao Algoritmo 8 se encontram

nas linhas 1-5, 6 e 9-10. Nas linhas 1-5 ´e executada a busca em profundidade. Assim, o

n´o i ou j n˜ao ´e inclu´ıdo na busca, permitindo que a tabela de consultas mapeie apenas

uma das sub-´arvores T

ou T

. Com isso, a linha 6 limita a busca de forma que a aresta

A(f) = (i, j) n˜ao precise ser veriﬁcada, j´a que ela n˜ao foi removida da AGM. Por ﬁm, as

linhas 9-10 s˜ao executadas quando uma aresta (x, y) = (i, j) ´e encontrada, removendo a

aresta incrementada e adicionando a aresta (x, y).

5.3 Algoritmo para Incremento no Custo de Arestas 49

Algoritmo 9 Incremento no custo de uma aresta utilizando DRD-trees

Entrada: AGM T = (V, E



) (possivelmente desatualizada), a aresta (i, j) cujo custo foi

incrementado, os ponteiros p e f para a lista A e os custos w.

1: se i = parent(j) ent˜ao

2: Executar uma busca em profundidade a partir do n´o j, armazenando cada n´o visi-

tado no vetor de consultas δ com o valor verdadeiro. Para os outros n´os, δ deve

conter o valor falso;

3: sen˜ao

4: Executar uma busca em profundidade a partir do n´o i, armazenando cada n´o visi-

tado no vetor de consultas δ com o valor verdadeiro. Para os outros n´os, δ deve

conter o valor falso;

5: ﬁm se

6: enquanto p = f fa¸ca

7: (x, y) ← A(p);

8: se δ[x] = δ[y] ent˜ao

9: Cut(i, j);

10: Link(x, y, w(x, y));

11: retorne a ´arvore geradora m´ınima atualizada T ;

12: ﬁm se

13: p ← p + 1;

14: ﬁm enquanto

{Neste ponto, a estrutura da AGM n˜ao ser´a alterada, mas seu custo sim.}

15: se i = parent(j) ent˜ao

16: ω[j] ← w(i, j);

17: sen˜ao

18: ω[i] ← w(i, j);

19: ﬁm se

20: retorne a ´arvore geradora m´ınima atualizada T ;

O Algoritmo 9 tem sua corretude mantida pelo Teorema 5.1, mas sua complexidade

´e ligeiramente diminu´ıda, conforme o Teorema 5.3.

Teorema 5.3 O Algoritmo 9 utiliza tempo O(m) para atualizar a ´arvore geradora m´ınima

T .

Prova A complexidade para iniciar o vetor de consultas ´e de Θ(n), j´a que, embora no

m´aximo n−1 n´os ser˜ao visitados, exatamente n posi¸c˜oes de mem´oria ter˜ao de ser alocadas.

Como a reordena¸c˜ao das arestas ´e feita em O(m), e as O(m) consultas sobre conectividade

podem ser executadas em O(1) cada, chega-se `a complexidade de O(m) para atualizar a

AGM atrav´es do Algoritmo 9 quando considerado o pior caso.

5.4 Resumo do Cap´ıtulo 50

Este cap´ıtulo propˆos um algoritmo para a atualiza¸c˜ao de uma ´arvore geradora m´ınima de

um grafo sujeito a altera¸c˜oes dinˆamicas nos custos de suas arestas. O algoritmo proposto

´e ﬂex´ıvel, podendo ser utilizado para atualizar AGMs armazenadas sob qualquer estrutura

de dados para representa¸c˜ao de ´arvores dinˆamicas. Embora tenha complexidade te´orica

superior se comparada `a complexidade do algoritmo polilogar´ıtmico de Holm et al. [31],

espera-se deste algoritmo um bom desempenho pr´atico, j´a que ´e baseado em estruturas

de dados simples (a citar as DRD-trees propostas no Cap´ıtulo 4).

Foram realizados diversos experimentos para veriﬁcar a aplicabilidade dos algoritmos e

estruturas de dados propostos nos cap´ıtulos anteriores. Este cap´ıtulo foi dividido em duas

se¸c˜oes, que respectivamente analisam o desempenho da estrutura de dados DRD-trees

(Se¸c˜ao 6.1) e dos algoritmos para atualiza¸c˜ao de ´arvores geradoras m´ınimas em grafos

dinˆamicos (Se¸c˜ao 6.2).

Para todos os experimentos foi utilizado um computador PC Intel Pentium 4 HT com

freq

uˆencia de 3,2 GHz, mem´oria f´ısica de 512 MBytes e sistema operacional Slackware

GNU/Linux vers˜ao 10.2, com kernel Linux e compilador GNU g++. As vers˜oes de kernel

e compilador foram, respectivamente, 2.6.16 e 3.4.6. Os algoritmos e estruturas de dados

foram codiﬁcados em linguagem C++ padr˜ao ANSI/ISO e compilados atrav´es do comando

g++ -O3 -mcpu=pentium4, que otimiza o c´odigo bin´ario gerado. N˜ao foram permitidos

acessos `a mem´oria secund´aria (swap) atrav´es do comando swapoff, existente no sistema

operacional GNU/Linux. Todos os resultados foram obtidos a partir de seq

uˆencias de

atualiza¸c˜oes distintas, geradas a partir de dez sementes diferentes. Os tempos foram

contabilizados em segundos e representam a execu¸c˜ao de todas as opera¸c˜oes de atualiza¸c˜ao

`as quais os algoritmos foram submetidos.

Esta se¸c˜ao procurou comparar a estrutura de dados DRD-trees, proposta no Cap´ıtulo 4,

com as estruturas RD-trees, ST-trees e ET-trees (detalhadas na Tabela 6.1). Para isso,

foram realizados os experimentos apresentados na Tabela 6.2.

A Tabela 6.1 apresenta as estruturas de dados avaliadas nessa se¸c˜ao. Deve-se observar

que a estrutura DRD-C (DRD-trees com consultas r´apidas) depende da execu¸c˜ao pr´evia

6.1 Estruturas de Dados:

Arvores Dinˆamicas 52

Tabela 6.1: Estruturas de dados analisadas experimentalmente.

Estruturas de dados Denomina¸c˜ao Opera¸c˜ao de conectividade Complexidade

RD-trees RD Root(u) = Root(v) O(n)

DRD-trees DRD-R Root(u) = Root(v) O(n)

DRD-trees DRD-C Connected(u, v) O(1)

ST-trees ST Root(u) = Root(v) O(log n)

ET-trees ET Root(u) = Root(v) O(log n)

da opera¸c˜ao de busca em profundidade (com complexidade O(n)), o que ir´a garantir

complexidade constante quando amortizada sobre n chamadas `a fun¸c˜ao Connected. Por

outro lado, no caso da estrutura DRD-R, a opera¸c˜ao de conectividade deve buscar pela raiz

da ´arvore contendo o dado v´ertice.

Tabela 6.2: Experimentos sobre estruturas de dados para ´arvores dinˆamicas.

Experimento Descri¸c˜ao Objetivo

CAA Conectividade em ´arvores aleat´orias Desempenho no caso m´edio

CAL Conectividade em ´arvores lineares Desempenho no pior caso

CAB Conectividade em ´arvores balanceadas Overhead das estruturas

UAA Conectividade em ´arvores aleat´orias Overhead das DRD-trees

LAA Link e cut em ´arvores aleat´orias Desempenho geral

Na Tabela 6.2 encontram-se os experimentos realizados sobre as estruturas de dados

da Tabela 6.1. Todos os experimentos foram executados em ´arvores com n´umero de n´os

n ∈ {2000, 4000, . . . , 400000}. Os v´ertices e arestas escolhidos para as opera¸c˜oes acima

foram aleatoriamente selecionados.

Para os quatro primeiros experimentos, procurou-se observar o comportamento das

estruturas de dados quando submetidas a uma seq

uencia de k = 100000 consultas de

conectividade sobre os v´ertices i e j escolhidos aleatoriamente, para assim precisar seu

desempenho em casos onde a ´arvore ´e aleat´oria, linear ou balanceada. Para ´arvores

aleat´orias s˜ao geradas n − 1 arestas de maneira aleat´oria, sem que hajam ciclos. J´a

´arvores lineares s˜ao constru´ıdas atrav´es das arestas (1, 2), (2, 3), ..., (n − 1, n). Por ﬁm,

´arvores balanceadas s˜ao ´arvores completas, ou seja, de altura logar´ıtmica.

Os resultados para os experimentos CAA, CAL e CAB s˜ao apresentados nas Figuras 6.1,

6.2 e 6.3, respectivamente.

A Figura 6.1 traz o desempenho em caso m´edio da opera¸c˜ao para veriﬁca¸c˜ao de conecti-

6.1 Estruturas de Dados:

Arvores Dinˆamicas 53

0.2

0.4

0.6

0.8

1.2

1.4

1.6

1.8

0 50000 100000 150000 200000 250000 300000 350000 400000

Tempos de CPU (segundos)

Número de vértices

DRD−R

DRD−C

Figura 6.1: Tempos de CPU para a execu¸c˜ao de 100000 consultas de conectividade em

´arvores aleat´orias.

vidade das estruturas de dados analisadas. Nessa ﬁgura, observa-se o comportamento pra-

ticamente constante da estrutura DRD-C, em conformidade com sua complexidade te´orica.

Este fato tamb´em pode ser veriﬁcado em todas as outras estruturas de dados. Aquelas de

complexidade linear, nominalmente RD e DRD-R, possuem curvas praticamente idˆenticas,

o que ´e facilmente justiﬁc´avel: ambas estruturas possuem implementa¸c˜oes idˆenticas da

opera¸c˜ao Root. J´a as estruturas de complexidade logar´ıtmica apresentam desempenho

diferenciado: a estrutura ET, uma implementa¸c˜ao da estrutura de dados ET-trees, realiza

consultas de conectividade com tempos visivelmente mais baixos que a implementa¸c˜ao da

estrutura de dados ST-trees. Cabe ainda a compara¸c˜ao entre as estruturas de complexi-

dade linear com aquelas de complexidade logar´ıtmica. Em compara¸c˜ao com a estrutura

ET-trees, as estruturas lineares s˜ao mais r´apidas em ´arvores com at´e aproximadamente

50000 n´os. J´a com a estrutura de dados ST-trees, o cruzamento das curvas de desempenho

ocorre pr´oximo aos 500000 n´os (n˜ao se encontra no gr´aﬁco).

Na Figura 6.2 s˜ao apresentados os resultados para ´arvores de altura linear. Tais ´arvores

representam o pior caso para as estruturas de dados RD-trees e DRD-trees (nessa ´ultima,

quando ´e utilizada a consulta atrav´es da opera¸c˜ao Root). No gr´aﬁco apresentado, pode-se

veriﬁcar que esse pior caso realmente ocorre na pr´atica. Todas as outras estruturas de

dados mantiveram o comportamento esperado (em conformidade com a teoria) quando

utilizadas para representar ´arvores com altura linear.

6.1 Estruturas de Dados:

Arvores Dinˆamicas 54

0.03125

0.0625

0.125

0.25

0.5

0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

Tempos de CPU (segundos)

Número de vértices

DRD−R

DRD−C

Figura 6.2: Tempos de CPU para a execu¸c˜ao de 100000 consultas de conectividade em

´arvores lineares.

0.2

0.4

0.6

0.8

1.2

1.4

1.6

1.8

0 50000 100000 150000 200000 250000 300000 350000 400000

Tempos de CPU (segundos)

Número de vértices

DRD−R

Figura 6.3: Tempos de CPU para a execu¸c˜ao de 100000 consultas de conectividade em

´arvores balanceadas.

O experimento cujos resultados s˜ao apresentados na Figura 6.3 faz uma an´alise da

sobrecarga introduzida pelas estruturas de dados projetadas para garantir complexidades

logar´ıtmicas, analisando para isso o melhor caso de entrada para as estruturas de dados.

Esse experimento consistiu em realizar consultas de conectividade em ´arvores completas,

6.1 Estruturas de Dados:

Arvores Dinˆamicas 55

ou seja, de altura logar´ıtmica, representando ent˜ao o melhor caso de entrada para as

estruturas. Nesse cen´ario, todas as estruturas de dados, com exce¸c˜ao da DRD-C (essas

continuam com a opera¸c˜ao de conectividade executada em tempo constante), passam a

oferecer opera¸c˜oes com complexidades logar´ıtmicas (para as estruturas DRD-R e RD, subir

em uma ´arvore tem complexidade O(log n) se a altura desta ´e logar´ıtmica). Com isso,

a estrutura RD ´e utilizada como base dessa an´alise por ser uma implementa¸c˜ao direta de

´arvores dinˆamicas. Pode-se observar atrav´es da Figura 6.3 que, dentre as estruturas com

opera¸c˜oes de complexidade logar´ıtmica, as ET-trees possuem a menor sobrecarga sobre

sua estrutura, comprovando assim o que j´a foi analisado teoricamente no Cap´ıtulo 3.

Cabe aqui ressaltar que todas as estruturas se comportaram perfeitamente de acordo

com suas an´alises te´oricas. As estruturas RD e DRD-R possuem curvas lineares em todos os

casos, com exce¸c˜ao das instˆancias de ´arvores com altura logar´ıtmica. Por outro lado, as

estruturas ET e ST se comportam sempre de maneira logar´ıtmica, o mesmo acontecendo

com a estrutura DRD-C, desta vez apresentando comportamento constante.

Para completar os experimentos de conectividade, faz-se necess´aria a veriﬁca¸c˜ao do

impacto da busca em profundidade na estrutura de dados DRD-C. Para isso foi desenvolvido

o seguinte ambiente para testes, tendo como base a ´arvore T = (V, E



), n = 500000 e o

n´umero de consultas ﬁxado em k = 100000: a cada l = 1000, 2000, . . . , 100000 consultas

realizadas, uma aresta (x, y) ∈ T ´e aleatoriamente escolhida para ser removida da ´arvore

ou uma aresta (x, y) /∈ T ´e aleatoriamente escolhida para ser inserida em T , desde que

(x, y) n˜ao introduza ciclos nessa ´arvore. Embora os tempos dessas opera¸c˜oes n˜ao tenham

sido contabilizados, a tabela de consultas da estrutura DRD-trees teve de ser recalculada.

Assim, este experimento analisa a sobrecarga introduzida pelas freq

uentes chamadas `a

opera¸c˜ao de busca em profundidade nas DRD-trees. Note que a complexidade anunciada

pela Equa¸c˜ao 4.1 ser´a violada, j´a que o argumento de amortiza¸c˜ao n˜ao ser´a mais v´alido.

O comportamento da estrutura DRD-C na Figura 6.4 ´e compat´ıvel com a seguinte an´a-

lise: se uma busca em profundidade ´e realizada a cada l opera¸c˜oes, ent˜ao a complexidade

do m´etodo ´e de O((n + l · O(1))/l) = O(n/l). Como l inicialmente vale 1000 e n ´e ﬁ-

xado em 500000, a complexidade nesse caso ´e O(n), j´a que n  l. Conforme l → n, a

complexidade das opera¸c˜oes tendem a O(1). Isto explica o comportamento constante do

algoritmo quando l > 50000, ou seja, o valor de l chegou ao limiar do impacto causado

pela busca em profundidade nas consultas de conectividade.

Finalizando a se¸c˜ao de experimentos em ´arvores dinˆamicas, a Figura 6.5 apresenta

os resultados para seq

uˆencias de links e cuts. Esses resultados se mostram condizentes

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 56

0.25

0.5

0 20000 40000 60000 80000 100000 120000 140000

Tempos de CPU (segundos)

Iterações para atualização da árvore

DRD−R

DRD−C

Figura 6.4: Tempos de CPU para a execu¸c˜ao de 100000 consultas de conectividade em

´arvores aleat´orias sujeitas altera¸c˜oes estruturais.

com as an´alises te´oricas. Para a estrutura de dados RD, opera¸c˜oes de link e cut tiveram

complexidades lineares, visto que certas arestas s´o podem ser inseridas mediante uma

opera¸c˜ao de Evert. Por outro lado, a estrutura DRD-R (aqui representando as DRD-trees)

foi aquela que apresentou a maior complexidade nesse experimento, j´a que existe o custo

de se pro curar por n´os dentro da lista de ﬁlhos de um n´o quando se executam opera¸c˜oes

sobre essa estrutura. Por ﬁm, as duas outras estruturas se comportaram logaritmicamente,

de acordo com as perspectivas estabelecidas pela an´alise te´orica.

Nesta se¸c˜ao ´e realizada a an´alise experimental dos algoritmos para atualiza¸c˜ao da ´arvore

geradora m´ınima de um grafo dinˆamico. Para tanto, foram utilizados dois conjuntos de

instˆancias de forma a compatibilizar os resultados deste trabalho com aqueles apresentados

em [4, 10] (Se¸c˜ao 6.2.1) e ao mesmo tempo oferecer uma an´alise mais abrangente, a partir

de instˆancias de problemas reais e tamb´em de instˆancias com grande n´umero de v´ertices

e arestas (Se¸c˜ao 6.2.2). Os algoritmos analisados s˜ao apresentados na Tabela 6.3.

Os algoritmos do grupo C foram implementados de acordo com o trabalho [10]: para

o grafo G = (V, E) de AGM T = (V, E



), uma ´arvore balanceada do tipo AVL ´e utilizada

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 57

0.125

0.25

0.5

0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

Tempos de CPU (segundos)

Número de vértices

DRD−R

Figura 6.5: Tempos de CPU para a execu¸c˜ao de 100000 opera¸c˜oes mistas de link e cut.

Tabela 6.3: Algoritmos analisados experimentalmente.

Grupo Algoritmo Referˆencia Estrutura de dados Complexidade

C C(ET+ST) Cattaneo et al. [10] ET-trees e ST-trees O(m log n)

C-Mod(DRD+ST) Modiﬁcado de [10] DRD-trees e ST-trees O(m)

RT RT(RD) Esta disserta¸c˜ao RD-trees O(mn)

RT(DRD) Esta disserta¸c˜ao DRD-trees O(m)

RT(ST) Esta disserta¸c˜ao ST-trees O(m log n)

RT(ET+ST) Esta disserta¸c˜ao ET-trees e ST-trees O(m log n)

RT(DRD+ST) Esta disserta¸c˜ao DRD-trees e ST-trees O(m)

para armazenar as arestas de E − E



enquanto duas estruturas de ´arvores dinˆamicas

s˜ao utilizadas para armazenar T . Quando uma aresta tem seu peso atualizado, duas

opera¸c˜oes s˜ao realizadas: uma remo¸c˜ao, seguida de uma inser¸c˜ao. A primeira opera¸c˜ao

realiza a remo¸c˜ao da aresta (i, j) e ´e assim executada: se (i, j) ∈ E



, ela ´e ent˜ao removida

de E



. Depois disso, uma aresta substituta (x, y) ´e buscada dentre as arestas da ´arvore

AVL, partindo da aresta de menor custo e percorrendo esta estrutura em ordem. Se

toda a AVL foi percorrida e nenhuma aresta conecta as ´arvores T

e T

, ent˜ao T ﬁcar´a

temporariamente desconectada. A segunda opera¸c˜ao corresponde `a inser¸c˜ao da aresta

(i, j) com o novo peso w(i, j) e ´e executada da seguinte forma. Veriﬁca-se em T se os

v´ertices i e j encontram-se conectados. Em caso positivo, (i, j) s´o ´e adicionada a T se a

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 58

aresta (x, y) de maior custo no caminho entre i e j satisfaz a desigualdade w(x, y) > w(i, j).

Nesse caso, (x, y) ´e removida de T atrav´es da opera¸c˜ao Cut(x, y) e (i, j) ´e adicionada a T

atrav´es da opera¸c˜ao Link(i, j, w(i, j)). Em caso contr´ario, (i, j) ´e adicionada a T atrav´es

da opera¸c˜ao Link(i, j, w(i, j)).

Os algoritmos do grupo RT foram aqueles apresentados no Cap´ıtulo 5, onde foram

utilizadas diferentes estruturas de dados para representa¸c˜ao da ´arvore geradora m´ınima.

Esta se¸c˜ao compara os algoritmos e estruturas de dados propostos utilizando o mesmo

parˆametro de Cattaneo et al. [10]. Assim, foram executados experimentos apenas so-

bre grafos sint´eticos. Os experimentos foram divididos em aleat´orios, onde os grafos s˜ao

aleatoriamente gerados, e k-Cliques, que sintetizam o pior caso dos algoritmos aqui imple-

mentados atrav´es da utiliza¸c˜ao de grafos contendo k cliques com c n´os cada e apenas 2k

arestas inter-clique (diﬁcultando a busca por arestas substitutas em atualiza¸c˜oes aplicadas

a arestas inter-clique). A Tabela 6.4 apresenta os experimentos sint´eticos realizados neste

trabalho.

Tabela 6.4: Experimentos sint´eticos realizados. Para o experimento k-Clique, n = k · c e

m = 2 · k + (c · (c − 1))/2, onde k representa o n´umero de cliques e c o n´umero de v´ertices

em cada clique.

Experimento n m Incrementos Decrementos

Aleat´orio (1) 1000 1000 ∼ 100000 10000 10000

Aleat´orio (2) 2000 1000 ∼ 100000 10000 10000

Aleat´orio (3) 4000 1000 ∼ 100000 10000 10000

k-Clique (1) 2000 (k = 4, c = 500) 499008 10000 10000

k-Clique (2) 2000 (k = 10, c = 200) 199020 10000 10000

k-Clique (3) 2000 (k = 20, c = 100) 99040 10000 10000

k-Clique (4) 2000 (k = 40, c = 50) 49080 10000 10000

k-Clique (5) 2000 (k = 50, c = 40) 39100 10000 10000

k-Clique (6) 2000 (k = 100, c = 20) 19200 10000 10000

k-Clique (7) 2000 (k = 200, c = 10) 9400 10000 10000

k-Clique (8) 2000 (k = 500, c = 4) 4000 10000 10000

Com os experimentos Aleat´orio (1), Aleat´orio (2) e Aleat´orio (3), objetiva-se analisar

os comportamentos dos algoritmos em um grafo sint´etico quando variam-se o n´umero de

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 59

arestas. Os grafos foram gerados aleatoriamente. Os resultados desses experimentos est˜ao

sintetizados nas Figuras 6.6, 6.7 e 6.8.

0.031

0.062

0.125

0.250

0.500

1.000

2.000

4.000

8.000

16.000

0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

Tempos de CPU (segundos)

Número de arestas

C−Mod(DRD+ST)

C(ET+ST)

RT(Sort)

RT(RD)

RT(DRD)

RT(ST)

RT(ET+ST)

RT(DRD+ST)

Figura 6.6: Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes aleat´orias de custos

em grafos aleat´orios contendo 1000 v´ertices.

A Figura 6.6 exibe os resultados dos experimentos em grafos gerados aleatoriamente,

sujeitos a seq

uˆencias aleat´orias de atualiza¸c˜oes nos custos de suas arestas. Tais seq

uˆencias

de atualiza¸c˜oes s˜ao caracterizadas pela grande quantidade de opera¸c˜oes caras em grafos

esparsos, correspondendo a incrementos de custos em arestas da AGM. Com isso, todos os

algoritmos s˜ao obrigados a buscar por uma aresta substituta, de menor peso, a cada atua-

liza¸c˜ao, resultando no elevado tempo computacional de todos os m´etodos quando o grafo

´e esparso (contendo at´e 5000 arestas). Por outro lado, conforme o grafo torna-se denso,

seq

uˆencias caras de atualiza¸c˜oes tornam-se raras, pois probabilisticamente incrementam-

se custos de arestas que n˜ao se encontram na AGM. Isso explica o comportamento dos

algoritmos quando o n´umero de arestas varia de 10000 a 100000: para aqueles da classe

RT, apenas o tempo de reordena¸c˜ao exerce impacto nos resultados; j´a para aqueles da

classe C, onde n˜ao existe reordena¸c˜ao, seus tempos ﬁcam praticamente est´aveis. Dentre as

curvas apresentadas ser´a destacado o tempo de CPU que os algoritmos RT consomem para

reordenar a lista de arestas, sob a denomina¸c˜ao RT(Sort). Embora este tempo j´a se en-

contre somado nos tempos dos algoritmos propriamente ditos, decidiu-se por contabiliz´a-lo

tamb´em separadamente, o que permite uma an´alise mais abrangente do impacto da reor-

dena¸c˜ao nesses algoritmos.

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 60

Decrementos em arestas n˜ao pertencentes `a AGM n˜ao impactam diretamente nos

algoritmos, j´a que seu melhor caso ocorre quando o grafo ´e esparso. O pior caso para

opera¸c˜oes de decremento ocorre quando m  n, resultando em freq

uentes decrementos

em arestas n˜ao pertencentes `a AGM (que podem levar a altera¸c˜oes na AGM). Como os

tempos dos algoritmos foram maiores quando o grafo ´e esparso, chega-se a conclus˜ao que

as opera¸c˜oes que inﬂuenciam diretamente na complexidade dos algoritmos s˜ao aquelas de

incrementos em arestas da AGM.

Na Figura 6.6, a curva RT(Sort) indica que a reordena¸c˜ao da lista de arestas to-

mou praticamente todo o tempo dos algoritmos RT. Assim, conclui-se que os algoritmos

baseados em [10] s˜ao mais eﬁcientes na atualiza¸c˜ao de AGMs em grafos aleat´orios com

poucos v´ertices e muitas arestas. Destaca-se ainda o desempenho do algoritmo h´ıbrido C-

Mod(DRD+ST), que ´e sensivelmente o m´etodo mais r´apido para as condi¸c˜oes aqui analisadas

(grafos aleat´orios sujeitos a seq

uˆencias de atualiza¸c˜ao geradas aleatoriamente). Em grafos

esparsos, onde seq

uˆencias caras s˜ao processadas, os algoritmos RT s˜ao mais eﬁcientes.

0.062

0.125

0.250

0.500

1.000

2.000

4.000

8.000

16.000

32.000

0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

Tempos de CPU (segundos)

Número de arestas

C−Mod(DRD+ST)

C(ET+ST)

RT(Sort)

RT(RD)

RT(DRD)

RT(ST)

RT(ET+ST)

RT(DRD+ST)

Figura 6.7: Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes aleat´orias de custos

em grafos aleat´orios contendo 2000 v´ertices.

A Figura 6.7 traz os resultados para grafos com n = 2000 e experimentos idˆenticos

aos da Figura 6.6. Embora a ordem e a relevˆancia dos resultados n˜ao se alterem, nota-se

um deslocamento do ponto de interse¸c˜ao entre as curvas dos algoritmos RT com as curvas

dos algoritmos C.

Com o aumento do n´umero de v´ertices para n = 4000, veriﬁca-se que o desempenho do

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 61

0.125

0.250

0.500

1.000

2.000

4.000

8.000

16.000

32.000

64.000

0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

Tempos de CPU (segundos)

Número de arestas

C−Mod(DRD+ST)

C(ET+ST)

RT(Sort)

RT(RD)

RT(DRD)

RT(ST)

RT(ET+ST)

RT(DRD+ST)

Figura 6.8: Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes aleat´orias de custos

em grafos aleat´orios contendo 4000 v´ertices.

algoritmo RT(RD) ´e muito ruim quando aplicado a um grafo esparso e conforme aumenta

o n´umero de v´ertices. O deslocamento do ponto de interse¸c˜ao entre as curvas dos algo-

ritmos RT e C continua, explicado pelo aumento no n´umero de consultas de conectividade

realizadas pelos algoritmos C(ET+ST) e C-Mod(DRD+ST). Essas consultas, quando cresce o

n´umero de v´ertices, passam a gastar mais tempo de CPU, atingindo especiﬁcamente os

algoritmos do grupo C que, a cada incremento em arestas da AGM, procuram por uma

aresta substituta a partir da aresta de menor custo na ´arvore AVL. Mais eﬁcientes, os al-

goritmos RT iniciam essa busca a partir da aresta incrementada, economizando chamadas

ao m´etodo Connected das ´arvores dinˆamicas.

Concluindo esta se¸c˜ao, seq

uˆencias aleat´orias de atualiza¸c˜oes s˜ao caracterizadas por

constantes incrementos em arestas do sobconjunto E − E



(tratados em O(log n) pelos

algoritmos do grupo C) e decrementos em arestas da AGM, que conﬁguram seq

uˆencias

f´aceis de atualiza¸c˜ao, um fato que n˜ao ´e interessante para analisar experimentalmente um

algoritmo.

Esta se¸c˜ao pretende melhor desenvolver os experimentos da se¸c˜ao anterior, introduzindo

seq

uˆencias estruturadas de atualiza¸c˜oes. Essas seq

uˆencias se dividem em 10% de atuali-

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 62

za¸c˜oes aleat´orias e 90% de atualiza¸c˜oes estruturadas. Em rela¸c˜ao `as atualiza¸c˜oes estrutu-

radas, 90% delas s˜ao incrementos em custos de arestas da AGM e 10% s˜ao decrementos

em custos de arestas que n˜ao pertencem `a AGM. Com isso, for¸ca-se que as atualiza¸c˜oes

possam alterar a AGM com maior freq

uˆencia, resultando em um maior grau de diﬁculdade

para os algoritmos.

0.004

0.016

0.062

0.250

1.000

4.000

16.000

64.000

256.000

0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

Tempos de CPU (segundos)

Número de arestas

C−Mod(DRD+ST)

C(ET+ST)

RT(Sort)

RT(RD)

RT(DRD)

RT(ST)

RT(ET+ST)

RT(DRD+ST)

Figura 6.9: Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes estruturadas de custos

em grafos aleat´orios contendo 1000 v´ertices.

A Figura 6.9 inverte o panorama apresentado na se¸c˜ao anterior, onde atualiza¸c˜oes

aleat´orias eram processadas. Nesse caso os algoritmos do grupo RT possuem desempenho

muito melhor que aqueles do grupo C. Conforme cresce o n´umero de arestas, os algo-

ritmos que melhor processam atualiza¸c˜oes estruturadas s˜ao, respectivamente: RT(DRD)

e RT(DRD+ST). Os algoritmos RT(ST), C(ET+ST) e C-Mod(DRD+ST) n˜ao apresentam um

bom desempenho. Nota-se que as curvas dos algoritmos do grupo RT encontram-se muito

pr´oximas, visto que o n´umero de v´ertices do experimento ´e muito pequeno.

Na Figura 6.10 os tempos dos algoritmos come¸cam a se distanciar com a duplica¸c˜ao

do n´umero de v´ertices. Contudo, os resultados n˜ao se alteram com rela¸c˜ao `a Figura 6.9.

Por ﬁm, na Figura 6.11, pode-se veriﬁcar que, ao aumentar o n´umero de v´ertices,

as curvas dos algoritmos de RT tendem a se distanciar. Como os tempos de CPU dos

algoritmos RT(DRD) e RT(DRD+ST) permaneceram pr´oximos, estes parecem ser os melhores

algoritmos no experimento em quest˜ao.

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 63

0.016

0.062

0.250

1.000

4.000

16.000

64.000

256.000

0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

Tempos de CPU (segundos)

Número de arestas

C−Mod(DRD+ST)

C(ET+ST)

RT(Sort)

RT(RD)

RT(DRD)

RT(ST)

RT(ET+ST)

RT(DRD+ST)

Figura 6.10: Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes estruturadas de

custos em grafos aleat´orios contendo 2000 v´ertices.

0.062

0.250

1.000

4.000

16.000

64.000

256.000

1024.000

0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

Tempos de CPU (segundos)

Número de arestas

C−Mod(DRD+ST)

C(ET+ST)

RT(Sort)

RT(RD)

RT(DRD)

RT(ST)

RT(ET+ST)

RT(DRD+ST)

Figura 6.11: Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes estruturadas de

custos em grafos aleat´orios contendo 4000 v´ertices.

Na pr´oxima se¸c˜ao, analisa-se o desempenho dos algoritmos com rela¸c˜ao ao n´umero de

v´ertices.

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 64

Este experimento tem por objetivo analisar o impacto do n´umero de v´ertices nas estruturas

para ´arvores dinˆamicas, corrigindo uma deﬁciˆencia dos trabalhos [4, 10]. Acredita-se que

o impacto do n ´umero de v´ertices sobre o desempenho dos algoritmos ´e maior que o do

n´umero de arestas no desempenho dos algoritmos. Desta forma, ﬁxou-se o n´umero de

arestas em m = 99000, enquanto que o n´umero de v´ertices variou de n = 500 (grafo

denso) a 99000 (grafo esparso). Esses resultados s˜ao apresentados na Figura 6.12.

0.25

256

1024

4096

16384

65536

0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

Tempos de CPU (segundos)

Número de vértices

C−Mod(DRD+ST)

C(ET+ST)

RT(Sort)

RT(RD)

RT(DRD)

RT(ST)

RT(ET+ST)

RT(DRD+ST)

Figura 6.12: Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes aleat´orias de custos

em grafos aleat´orios contendo 99000 arestas.

Os resultados da Figura 6.12 mostram a inﬂuˆencia do n´umero de v´ertices sobre os

algoritmos implementados. Em primeiro lugar, pode-se atribuir a inﬂuˆencia no compor-

tamento dos algoritmos `a complexidade das opera¸c˜oes em ´arvores dinˆamicas, j´a que o

n´umero de arestas permaneceu inalterado. Os algoritmos que mais foram afetados pelo

aumento no n´umero de v´ertices foram RT(ST) e RT(RD), j´a que o primeiro possui uma es-

trutura de dados demasiadamente complexa (embora ofere¸ca opera¸c˜oes com complexidade

baixa) e o segundo possui uma estrutura de dados demasiadamente simples (oferecendo

opera¸c˜oes com complexidade muito elevada).

Outro ponto a se considerar ´e a raz˜ao entre o n´umero de arestas e de v´ertices do grafo,

ou seja, quando este ´e esparso ou denso. Para grafos densos, todos os algoritmos possuem

comportamento parecido, uma vez que opera¸c˜oes complexas s˜ao realizadas poucas vezes

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 65

e que ´e f´acil encontrar arestas substitutas quando uma opera¸c˜ao complexa ´e executada.

Quando o grafo come¸ca a ﬁcar esparso, a quantidade de opera¸c˜oes caras come¸ca a in-

ﬂuenciar no comp ortamento de todos os algoritmos. Entretanto, para os algoritmos do

grupo C, existe um limiar pr´oximo a n = 70000 a partir do qual os tempos computacionais

come¸cam a cair. Isto ´e explicado pela quantidade de arestas armazenadas na ´arvore AVL,

que diminui progressivamente at´e restar apenas uma (quando n = 99000). Para os algo-

ritmos de RT, o invervalo entre 95000 e 99000 v´ertices ´e cr´ıtico pela crescente quantidade

de opera¸c˜oes que alteram a AGM. De fato, os algoritmos do grupo C s˜ao eﬁcientes quando

utilizados em grafos onde n ≈ m justamente pela baixa quantidade de arestas na ´arvore

AVL.

Por ﬁm, faz-se necess´aria a an´alise do comportamento do algoritmo RT(ET+ST) quando

n ≈ m, j´a que, enquanto todos os algoritmos de seu grupo apresentaram um not´avel

aumento em seus tempos de CPU, este apresentou uma ligeira queda. Atrav´es de um

exame de proﬁling [36], foi observado que a diminui¸c˜ao dos tempos se deu pela quase

inexistˆencia de altera¸c˜oes na AGM, o que traz a conclus˜ao de que boa parte da sobrecarga

deste algoritmo se encontra na atualiza¸c˜ao de ambas as ´arvores dinˆamicas, e n˜ao nas

consultas sobre conectividade.

Esta se¸c˜ao introduz o experimento de atualiza¸c˜oes aleat´orias em grafos k-Clique. A Fi-

gura 6.13 traz os resultados para os experimentos k-Clique da Tabela 6.4.

O gr´aﬁco da Figura 6.13 mostra que n˜ao h´a mudan¸cas no comp ortamento dos algo-

ritmos mesmo quando ocorrem opera¸c˜oes muito custosas, uma vez que a probabilidade

de altera¸c˜oes em arestas inter-clique ´e muito baixa. Assim, a ordem dos resultados se

manteve idˆentica `aquela apresentada nos experimentos em grafos aleat´orios.

Nesta se¸c˜ao s˜ao apresentados os resultados para 20000 opera¸c˜oes de incremento nos cus-

tos de arestas inter-cliques, o que resulta no pior caso para todos os algoritmos aqui

apresentados. Os resultados s˜ao sintetizados na Figura 6.14.

Atrav´es da Figura 6.14 ´e observado que o comportamento dos algoritmos do grupo

RT, quando implementados utilizando boas estruturas de dados para manuten¸c˜ao de ´ar-

vores dinˆamicas (todas as estruturas com exce¸c˜ao das RD-trees e ST-trees), ´e superior

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 66

0.125

0.25

0.5

0 50000 100000 150000 200000 250000 300000 350000 400000 450000 500000

Tempos de CPU (segundos)

Número de arestas (m)

C−Mod(DRD+ST)

C(ET+ST)

RT(Sort)

RT(RD)

RT(DRD)

RT(ST)

RT(ET+ST)

RT(DRD+ST)

Figura 6.13: Tempos de CPU para a execu¸c˜ao de 20000 atualiza¸c˜oes aleat´orias de custos

em grafos k-Clique.

0.062

0.250

1.000

4.000

16.000

64.000

256.000

1024.000

4096.000

0 50000 100000 150000 200000 250000 300000 350000 400000 450000 500000

Tempos de CPU (segundos)

Número de arestas (m)

C−Mod(DRD+ST)

C(ET+ST)

RT(Sort)

RT(RD)

RT(DRD)

RT(ST)

RT(ET+ST)

RT(DRD+ST)

Figura 6.14: Tempos de CPU para a execu¸c˜ao de 20000 opera¸c˜oes de incremento em

arestas inter-clique.

ao comportamento dos algoritmos do grupo C. Isto se d´a pelo eﬁciente sistema de busca

executado pelo primeiro grupo, onde in´umeras arestas s˜ao eliminadas da veriﬁca¸c˜ao de

conectividade.

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 67

Novamente os melhores algoritmos para esta conﬁgura¸c˜ao de entrada s˜ao RT(DRD) e

RT(DRD+ST). Tomando por base a curva RT(Sort) das Figuras 6.13 e 6.14, que ´e limitante

inferior dos algoritmos do grupo RT, ﬁca claro que, mesmo aplicados a um conjunto de

instˆancias muito dif´ıcil, estes algoritmos possuem sobrecarga muito baixa para buscas por

arestas substitutas. Por outro lado, ainda fazendo um paralelo entre as Figuras 6.13 e

6.14, ´e vis´ıvel o aumento nos tempos de CPU dos algoritmos em C, inﬂuenciados pelas

complexas seq

uˆencias de atualiza¸c˜oes `as quais o grafo foi submetido. Mesmo assim, nesse

ambiente o algoritmo h´ıbrido C-Mod(DRD+ST) foi superior ao algoritmo C(ET+ST).

Nota-se que experimentos dessa natureza n˜ao s˜ao os melhores para simular ambientes

reais em algoritmos dinˆamicos, pois grafos k-Clique s˜ao muito espec´ıﬁcos e criados apenas

com a ﬁnalidade de induzir o pior caso nos algoritmos C e RD e favorecer os algoritmos de

Holm et al. [30, 31] e de Frederickson [17, 18], detalhados no Cap´ıtulo 3.

Esta se¸c˜ao avaliou experimentalmente os algoritmos da Tabela 6.3 utilizando para isto um

conjunto sint´etico de instˆancias. Foram executados, para grafos aleatoriamente gerados,

experimentos aleat´orios (Se¸c˜ao 6.2.1.1) e estruturados (Se¸c˜ao 6.2.1.2). Para os experi-

mentos da Se¸c˜ao 6.2.1.1, os algoritmos do grupo C obtiveram melhor comportamento, j´a

que nesse experimento os algoritmos s˜ao submetidos a seq

uˆencias que praticamente n˜ao

alteram a AGM do grafo. Ainda assim, veriﬁcou-se que a estrutura de dados DRD-trees

conseguiu diminuir ainda mais os tempos obtidos por este grupo de algoritmos. Por outro

lado, na Se¸c˜ao 6.2.1.5, os algoritmos s˜ao submetidos a seq

uˆencias caras de atualiza¸c˜ao,

com 90% delas sendo incrementos em arestas da AGM ou decrementos em arestas de

E − E



. Nesse ambiente, os algoritmos RT(DRD) e RT(DRD+ST) se destacam perante os

demais, com tempos substancialmente menores que aqueles obtidos pelos algoritmos do

grupo C.

Complementarmente, a Se¸c˜ao 6.2.1.3 trouxe um experimento onde variou-se o n´umero

de v´ertices do grafo. Novamente, os algoritmos RT foram mais eﬁcientes para este conjunto

de instˆancias, excetuando-se o caso de grafos onde n ≈ m.

Por ﬁm, as Se¸c˜oes 6.2.1.4 e 6.2.1.5 trouxeram resultados para instˆancias k-Clique, onde

s˜ao gerados grafos compostos por k cliques de c n´os cada. Este conjunto de instˆancias,

utilizado em [10], ´e formado por oito grafos de 2000 arestas cada, variando-se os valores de

k e c. Na Se¸c˜ao 6.2.1.4 foram analisados os tempos de CPU dos algoritmos para seq

uˆencias

aleat´orias de atualiza¸c˜oes, onde os algoritmos do grupo C obtiveram melhores resultados.

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 68

Finalmente, na Se¸c˜ao 6.2.1.5 mostrou-se os tempos de CPU para seq

uˆencias estruturadas

de atualiza¸c˜oes em grafos k-Clique, consistindo em incrementar ou decrementar arestas

inter-cliques. Estas seq

uˆencias de atualiza¸c˜oes s˜ao caras e os resultados mostraram que

os algoritmos RT(DRD) e RT(DRD+ST) s˜ao mais r´apidos.

Desta forma, conclui-se esta bateria de experimentos com a certeza de que os algorit-

mos propostos nesta disserta¸c˜ao s˜ao mais eﬁcientes que os do estado da arte da literatura

quando aplicados a seq

uˆencias dif´ıceis de atualiza¸c˜ao.

Os experimentos desta se¸c˜ao foram realizados sobre instˆancias dos DIMACS Implemen-

tation Challenges [15], uma competi¸c˜ao de algoritmos eﬁcientes para um determinado

problema. A nona edi¸c˜ao desta competi¸c˜ao foi direcionada a algoritmos para o problema

de caminho m´ınimo em grafos (PCM), de onde as instˆancias foram retiradas. Tais instˆan-

cias podem ser encontradas em [14]. Os grafos para esses problemas foram pr´e-processados

de forma a remover arestas redundantes, j´a que os mesmos s˜ao, em sua vers˜ao original,

orientados.

As instˆancias utilizadas s˜ao divididas em quatro grupos. O primeiro grupo, denomi-

nado Random4-n, cont´em grafos gerados aleatoriamente. Neste caso, existem tanto com-

ponentes contendo grupos de v´ertices com grande quantidade de arestas para conect´a-los

quanto componentes contendo grupos de v´ertices com p oucas arestas entre si (formando

longos caminhos entre os v´ertices, onde n˜ao existem op¸c˜oes de arestas para conect´a-los).

O grupo Long-n cont´em grafos com caminhos longos, privilegiando as boas estruturas de

dados para ´arvores dinˆamicas, j´a que as ´arvores geradoras m´ınimas ser˜ao compostas por

esses caminhos. O terceiro grupo, Square-n, procura concentrar os v´ertices em uma regi˜ao

limitada do plano, resultando em grafos com mais op¸c˜oes de arestas para substitui¸c˜ao que

o grupo Long-n. Por ﬁm, o grupo USA-road-d ´e composto por instˆancias reais, extra´ı-

das a partir do mapa rodovi´ario dos Estados Unidos da Am´erica. Estas instˆancias foram

divididas em regi˜oes, j´a que to do o mapa ´e formado por milh˜oes de v´ertices.

Para todos os grupos de instˆancias acima, com exce¸c˜ao ao grupo USA-road-d, o n´umero

de v´ertices varia de 1024 a 524288. O n´umero de arestas para o grupo Random4-n ´e cerca

de quatro vezes o n´umero de v´ertices, enquanto para os demais o n´umero de arestas

´e em torno de trˆes vezes o n´umero de v´ertices. Os custos das arestas se encontram no

intervalo [1, n], exceto para o grupo USA-road-d onde os custos s˜ao baseados nas distˆancias

geogr´aﬁcas entre os v´ertices do grafo.

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 69

Foram omitidos os tempos de execu¸c˜ao de alguns algoritmos que n˜ao processaram

todas as 20000 atualiza¸c˜oes `as quais foram submetidos ap´os 3600 segundos de execu-

¸c˜ao. Nas tabelas das pr´oximas se¸c˜oes, foram destacados em negrito os tempos de CPU

correspondentes aos algoritmos com melhor desempenho para cada instˆancia.

O primeiro grupo de experimentos, executado sobre todos os grupos de instˆancias, con-

sistiu em realizar 20000 atualiza¸c˜oes aleat´orias, com custos no intervalo [1, n], em arestas

tamb´em escolhidas aleatoriamente.

Primeiro, s˜ao apresentados e analisados os resultados da Tabela 6.5. Nela, observa-

se que o algoritmo C-Mod(DRD+ST) tem melhor desempenho para um maior n´umero de

v´ertices e arestas. Salienta-se a grande diferen¸ca de desempenho entre esta variante e o

algoritmo original, C(ET+ST). Dois outros algoritmos apresentam desempenho competi-

tivo com o algoritmo C-Mod(DRD+ST): RT(DRD) e RT(DRD+ST). Prejudicados pelo custo

da reordena¸c˜ao da lista de arestas a cada opera¸c˜ao, ainda assim estes algoritmos n˜ao

apresentaram desempenho signiﬁcativamente inferior `aquele. Por outro lado, os algorit-

mos RT(RD) e RT(ST) apresentaram resultados muito ruins, j´a que utilizam estruturas de

dados muito lentas para responder quest˜oes sobre conectividade.

Finaliza-se a an´alise da Tabela 6.5 com os resultados dos algoritmos C(ET+ST) e

RT(ET+ST).

A primeira vista, pode parecer estranho que o primeiro algoritmo tenha se

comportado de maneira superior ao segundo. Contudo, incrementos nos custos de arestas

de E − E



s˜ao tratados pelos algoritmos do grupo C atrav´es de simples inser¸c˜oes e remo-

¸c˜oes em ´arvores AVL, que s˜ao opera¸c˜oes de complexidade logar´ıtmica. Por outro lado,

algoritmos da classe RT precisam re-ordenar a lista de arestas, para ent˜ao constatar que a

opera¸c˜ao se deu sobre uma aresta do subconjunto E − E



. Al´em do custo da reordena¸c˜ao

da lista de arestas, os custos das opera¸c˜oes constantes nos algoritmos do grupo RT s˜ao um

pouco maiores que os apresentados nos algoritmos do grupo C. Desta forma, o algoritmo

C(ET+ST) mostrou-se superior ao algoritmo RT(ET+ST).

Na Tab ela 6.6 s˜ao apresentados os resultados dos algoritmos para as instˆancias Long-

n, que s˜ao mais dif´ıceis que as instˆancias Random4-n. O algoritmo de melhor desempenho

para este grupo de instˆancias foi o RT(DRD+ST), que obteve ligeira vantagem sobre o

algoritmo RT(DRD). Esta diferen¸ca se deu pela vantagem de se utilizar a estrutura ST-

trees nas opera¸c˜oes de decremento, pois lidou-se com um conjunto de instˆancias composto

por caminhos longos, o que exige boas implementa¸c˜oes da opera¸c˜ao Find_max.

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 70

Tabela 6.5: Tempos de CPU (segundos) para as instˆancias Random4-n ap´os 20000 atualiza¸c˜oes aleat´orias.

Instˆancia n m C-Mod(DRD+ST) C(ET+ST) RT(Sort) RT(RD) RT(DRD) RT(ST) RT(ET+ST) RT(DRD+ST)

Random4-n.10.0 1024 4080 0,53 0,81 0,14 0,50 0,29 6,08 0,69 0,41

Random4-n.11.0 2048 8178 0,76 1,43 0,27 1,11 0,55 13,22 1,18 0,63

Random4-n.12.0 4096 16372 1,23 3,41 0,55 2,64 1,06 28,55 3,11 1,10

Random4-n.13.0 8192 32748 2,33 8,80 1,22 7,30 2,12 63,13 8,74 2,26

Random4-n.14.0 16384 65524 4,73 23,35 2,49 20,50 4,33 142,05 24,15 4,28

Random4-n.15.0 32768 131055 9,95 68,04 4,95 53,95 8,21 322,68 68,39 8,17

Random4-n.16.0 65536 262122 20,48 197,47 11,47 180,40 17,59 772,52 202,06 17,39

Random4-n.17.0 131072 524273 40,02 540,06 30,39 1177,90 42,86 1971,35 583,93 41,83

Random4-n.18.0 262144 1048566 72,55 1332,88 64,11 3555,30 86,01 4390,44 1394,13 84,67

Random4-n.19.0 524288 2097139 129,63 3091,26 134,22 11622,00 177,51 10214,90 3315,53 175,23

Tabela 6.6: Tempos de CPU (segundos) para as instˆancias Long-n ap´os 20000 atualiza¸c˜oes aleat´orias.

Instˆancia n m C-Mod(DRD+ST) C(ET+ST) RT(Sort) RT(RD) RT(DRD) RT(ST) RT(ET+ST) RT(DRD+ST)

Long-n.10.0 1024 2944 0,70 1,08 0,09 1,05 0,35 8,53 0,88 0,50

Long-n.11.0 2048 5936 1,05 1,66 0,14 3,07 0,61 18,15 1,49 0,76

Long-n.12.0 4096 11808 1,75 3,58 0,27 11,11 1,20 39,25 3,76 1,25

Long-n.13.0 8192 23729 3,26 8,72 0,58 92,87 2,93 85,70 11,33 2,90

Long-n.14.0 16384 47601 7,28 24,64 1,26 514,02 6,53 191,38 32,32 6,33

Long-n.15.0 32768 95150 18,81 73,15 2,64 2317,89 14,12 433,01 90,84 12,63

Long-n.16.0 65536 190493 40,93 204,58 5,86 - 30,46 1031,34 273,55 25,77

Long-n.17.0 131072 380952 93,79 543,73 13,00 - 68,95 2484,13 753,75 57,44

Long-n.18.0 262144 761894 199,10 1305,59 28,37 - 150,23 5720,72 1860,72 124,70

Long-n.19.0 524288 1523343 416,26 2980,40 60,27 - 318,97 12915,40 4336,07 269,84

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 71

Tabela 6.7: Tempos de CPU (segundos) para as instˆancias Square-n ap´os 20000 atualiza¸c˜oes aleat´orias.

Instˆancia n m C-Mod(DRD+ST) C(ET+ST) RT(Sort) RT(RD) RT(DRD) RT(ST) RT(ET+ST) RT(DRD+ST)

Square-n.10.0 1024 2964 1,28 1,11 0,07 0,65 0,62 8,39 1,24 0,68

Square-n.11.0 2025 5938 1,70 1,75 0,13 1,80 0,93 17,97 1,75 0,94

Square-n.12.0 4096 12037 2,89 3,67 0,25 5,59 1,76 39,10 4,40 1,76

Square-n.13.0 8190 24283 4,32 8,92 0,58 31,30 3,30 87,05 12,13 3,22

Square-n.14.0 16384 48742 8,76 24,59 1,27 147,93 6,92 192,24 32,66 6,17

Square-n.15.0 32761 97634 19,61 72,95 2,37 662,02 10,65 427,74 90,93 10,28

Square-n.16.0 65536 195768 36,33 202,66 5,23 2423,81 17,87 1032,01 268,42 17,28

Square-n.17.0 131044 392136 61,94 515,46 12,49 - 36,50 2472,79 736,58 34,17

Square-n.18.0 262144 785034 110,97 1233,83 28,78 - 72,68 5747,83 1824,21 68,67

Square-n.19.0 524176 1570146 201,30 2803,96 63,47 - 144,76 13103,30 4258,94 138,41

Tabela 6.8: Tempos de CPU (segundos) para as instˆancias USA-road-d ap´os 20000 atualiza¸c˜oes aleat´orias.

Instˆancia n m RT(Sort) RT(DRD) RT(ET+ST) RT(DRD+ST)

USA-road-d.BAY 321269 443518 33,44 128,87 4068,04 126,80

USA-road-d.COL 435665 619686 50,47 171,35 5350,45 169,82

USA-road-d.FLA 1070375 1519253 139,27 391,99 15058,30 390,58

USA-road-d.NE 1524452 2185573 206,14 583,79 23920,80 586,46

USA-road-d.NW 1207944 1576690 144,23 421,13 17927,40 419,09

USA-road-d.NY 264345 424580 31,35 102,35 3048,38 101,30

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 72

Os resultados da Tabela 6.7 n˜ao mudam o panorama acima apresentado, embora a

distˆancia entre o desempenho dos algoritmos RT(DRD+ST) e RT(DRD) seja bem menor em

fun¸c˜ao da estrutura dos grafos do grupo Square-n (a ocorrˆencia de caminhos longos n˜ao

´e freq

uente).

O conjunto de instˆancais USA-road-d foi utilizado para analisar o comp ortamento dos

algoritmos propostos em um ambiente real ou ainda em um grafo de entrada composto

por uma grande quantidade de v´ertices e arestas. Pela Tabela 6.8, observa-se que os re-

sultados permanecem inalterados. Por´em, enquanto os algoritmos RT(DRD+ST) e RT(DRD)

obtiveram tempos extremamente bons, o algoritmo RT(ET+ST) se comportou de forma

muito ruim. Este comportamento tamb´em foi seguido pelos outros algoritmos, que, de-

vido a resultados preliminares, foram descartados. Na Tabela 6.8 n˜ao s˜ao apresentados os

tempos de CPU relativos aos algoritmos do grupo C, em raz˜ao de serem muito elevados

em compara¸c˜ao aos demais.

Por ﬁm, em uma an´alise geral, observa-se que os algoritmos propostos no Cap´ıtulo 5

s˜ao mais r´apidos do que aqueles j´a existentes na literatura. O ganho de tempo ´e conside-

r´avel, ainda que comparados com o algoritmo C-Mod(DRD+ST). Conclui-se que os melhores

algoritmos para este conjunto de instˆancias e esta conﬁgura¸c˜ao de atualiza¸c˜oes s˜ao os ba-

seados no algoritmo geral proposto no Cap´ıtulo 5, nominalmente os algoritmos RT(DRD)

e RT(DRD+ST). Este ´ultimo, em instˆancias com grande n´umero de v´ertices, se apresenta

como a melhor op¸c˜ao, uma vez que as ST-trees possuem opera¸c˜oes com tempo assintoti-

camente menor que as DRD-trees.

A pr´oxima se¸c˜ao segue com uma avalia¸c˜ao mais cuidadosa dos algoritmos propostos,

visto que atualiza¸c˜oes em arestas aleat´orias n˜ao fornecem um bom modelo para representar

o comportamento dos algoritmos. Nessas seq

uˆencias, muitas arestas que n˜ao p ertencem

`a AGM s˜ao incrementadas, ao mesmo tempo que muitas arestas da AGM s˜ao decremen-

tadas, o que ´e f´acil de se resolver e muito distante da realidade para casos onde se quer,

na verdade, perturbar a solu¸c˜ao inicial em favor de uma nova solu¸c˜ao (como ´e o caso de

buscas locais, por exemplo).

Apresenta-se nesta se¸c˜ao os resultados para seq

uˆencias com ap enas 10% de atualiza¸c˜oes

aleat´orias, enquanto que o restante ´e composto por atualiza¸c˜oes focadas em (a) incremen-

tar o custo de arestas da AGM e (b) decrementar o custo de arestas do grafo mas n˜ao da

AGM. O objetivo desses experimentos ´e for¸car a altera¸c˜ao freq

uente da AGM.

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 73

Tabela 6.9: Tempos de CPU (segundos) para as instˆancias Random4-n ap´os 20000 atualiza¸c˜oes estruturadas.

Instˆancia n m C-Mod(DRD+ST) C(ET+ST) RT(Sort) RT(RD) RT(DRD) RT(ST) RT(ET+ST) RT(DRD+ST)

Random4-n.10.0 1024 4080 1,64 3,50 0,06 0,31 0,37 5,37 0,65 0,55

Random4-n.11.0 2048 8178 3,35 8,84 0,11 0,84 0,65 12,59 1,18 0,81

Random4-n.12.0 4096 16372 7,35 29,63 0,27 2,06 1,22 31,16 3,13 1,40

Random4-n.13.0 8192 32748 18,90 96,73 0,58 6,84 2,27 80,60 10,25 2,59

Random4-n.14.0 16384 65524 50,06 283,26 1,42 22,03 4,51 211,93 34,88 4,85

Random4-n.15.0 32768 131055 104,21 849,97 3,32 71,27 9,36 545,17 112,12 9,64

Random4-n.16.0 65536 262122 201,07 2558,76 7,34 274,40 19,22 1452,86 362,24 19,42

Random4-n.17.0 131072 524273 254,03 - 8,19 1785,24 30,12 2424,00 853,67 30,30

Random4-n.18.0 262144 1048566 295,70 - 18,52 - 65,33 - 2453,94 64,58

Random4-n.19.0 524288 2097139 554,63 - 43,69 - 142,35 - 6536,71 141,99

Tabela 6.10: Tempos de CPU (segundos) para as instˆancias Long-n ap´os 20000 atualiza¸c˜oes estruturadas.

Instˆancia n m C-Mod(DRD+ST) C(ET+ST) RT(Sort) RT(RD) RT(DRD) RT(ST) RT(ET+ST) RT(DRD+ST)

Long-n.10.0 1024 2944 0,85 1,07 0,09 0,65 0,79 5,99 0,73 0,88

Long-n.11.0 2048 5936 1,88 2,01 0,09 2,05 0,63 12,60 0,97 0,81

Long-n.12.0 4096 11808 3,42 5,03 0,16 7,27 1,21 27,41 2,15 1,35

Long-n.13.0 8192 23729 6,88 13,85 0,36 59,09 2,61 59,59 6,39 2,68

Long-n.14.0 16384 47601 15,80 40,86 0,82 329,28 6,07 132,68 20,55 5,94

Long-n.15.0 32768 95150 39,64 94,11 1,75 1709,10 14,18 330,58 74,85 12,89

Long-n.16.0 65536 190493 86,34 285,06 3,99 - 28,97 816,44 264,84 27,23

Long-n.17.0 131072 380952 178,30 787,00 8,76 - 67,17 1930,90 822,80 61,12

Long-n.18.0 262144 761984 357,91 2029,79 19,53 - 148,92 - 2237,49 137,93

Long-n.19.0 524288 1523343 731,00 - 42,94 - 321,90 - 5508,47 297,70

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 74

Tabela 6.11: Tempos de CPU (segundos) para as instˆancias Square-n ap´os 20000 atualiza¸c˜oes estruturadas.

Instˆancia n m C-Mod(DRD+ST) C(ET+ST) RT(Sort) RT(RD) RT(DRD) RT(ST) RT(ET+ST) RT(DRD+ST)

Square-n.10.0 1024 2964 1,40 1,16 0,05 0,59 0,62 6,05 0,82 0,66

Square-n.11.0 2025 5938 2,15 1,98 0,09 1,62 1,04 12,57 1,15 1,16

Square-n.12.0 4096 12037 4,04 5,06 0,18 4,76 1,97 27,57 2,60 1,94

Square-n.13.0 8190 24283 7,05 14,17 0,39 22,49 2,50 60,78 6,40 2,59

Square-n.14.0 16384 48742 15,42 41,11 0,84 109,98 4,68 134,33 20,49 4,70

Square-n.15.0 32761 97634 36,05 98,54 1,83 582,57 9,71 325,64 73,53 9,29

Square-n.16.0 65536 195768 73,07 294,02 4,07 2015,87 18,67 818,78 262,84 18,23

Square-n.17.0 131044 392136 140,81 805,21 8,88 11702,30 37,97 1982,62 816,37 36,92

Square-n.18.0 262144 785034 264,06 2053,33 19,70 - 77,83 - 2198,69 75,88

Square-n.19.0 524176 1570146 500,72 - 44,21 - 156,67 - 5452,39 153,00

Tabela 6.12: Tempos de CPU (segundos) para as instˆancias USA-road-d ap´os 20000 atualiza¸c˜oes estruturadas.

Instˆancia n m C-Mod(DRD+ST) C(ET+ST) RT(Sort) RT(DRD) RT(ET+ST) RT(DRD+ST)

USA-road-d.BAY 321269 443518 129,53 1211,83 24,33 89,49 2328,03 82,80

USA-road-d.COL 435665 619686 190,72 1604,13 34,24 117,71 3189,87 110,44

USA-road-d.FLA 1070375 1519253 467,91 2234,94 98,37 264,02 9611,59 258,29

USA-road-d.NE 1524452 2185573 726,44 1207,91 148,34 406,74 15884,20 403,82

USA-road-d.NW 1207944 1576690 507,72 2596,91 99,06 276,76 11251,80 273,25

USA-road-d.NY 264345 424580 166,84 1391,26 22,93 73,47 1829,68 67,83

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 75

Na Tabela 6.9 os tempos dos algoritmos do grupo C n˜ao se mostraram competitivos,

j´a que essas atualiza¸c˜oes for¸cam mudan¸cas na AGM e fazem com que a busca por arestas

substitutas seja realizada. Este fato contribui tamb´em para a grande diferen¸ca entre o

m´etodo h´ıbrido C-Mod(DRD+ST) e o m´etodo C(ET+ST), visto que o uso de DRD-trees, em

casos onde o n´umero de consultas de conectividade ´e grande, melhora substancialmente o

desempenho do m´eto do h´ıbrido.

O comportamento dos algoritmos do grupo RT permaneceu inalterado para esta classe

de problemas. Isto ´e explicado pela maneira como esses algoritmos tratam as opera¸c˜oes

de incrementos em pesos de arestas, que elimina boa parte das arestas que s˜ao obrigato-

riamente analisadas nos algoritmos do grupo C. Para as Tabelas 6.10 e 6.11 os resultados

tamb´em n˜ao se alteraram, indicando que o melhor algoritmo para se trabalhar em incre-

mentos e decrementos estruturados ´e o algoritmo RT(DRD+ST), por oferecer uma maneira

consistente para se lidar com caminhos longos al´em de, ao mesmo tempo, ser robusto para

casos onde esta situa¸c˜ao n˜ao ocorre. Ainda, o algoritmo RT(DRD) tamb´em se destaca por

ter bom desempenho em grafos com grande quantidade de arestas e, ainda, por manter

esse desempenho em grafos esparsos, onde longos caminhos de v´ertices podem surgir. O

algoritmo C-Mod(DRD+ST) consumiu pelo menos duas vezes o tempo utilizado pelos algo-

ritmos mais r´apidos. O algoritmo RT(ET+ST) obteve o pior desempenho dos algoritmos

que puderam ter seus tempos medidos.

Na Tabela 6.12 encontram-se os resultados das execu¸c˜oes estruturadas em grafos da

classe USA-road-d, caracterizados por serem notadamente mais esparsos que os grafos dos

outros conjuntos de instˆancias de [15]. Assim, como a ´arvore AVL dos algoritmos C n˜ao

cont´em grande quantidade de arestas, foi melhor o desempenho do algoritmo C(ET+ST)

quando comparado com o algoritmo RT(ET+ST), visto que o ´ultimo analisa muitas arestas

que j´a se encontram na AGM, bem como boa parte das arestas que s˜ao tamb´em analisadas

pelo algoritmo C(ET+ST). Mesmo assim, o algoritmo h´ıbrido C(ET+ST) obteve tempos de

9,34 a 1,66 vezes maiores que o algoritmo C-Mod(DRD+ST). Conclui-se esta tabela com o

fato de o algoritmo RT(DRD+ST) ser a melhor op¸c˜ao para tal conjunto de instˆancias. Tˆem-

se ainda que o algoritmo RT(DRD) possui tempos muito bons, ﬁcando sempre a poucos

segundos das execu¸c˜oes do algoritmo RT(DRD+ST).

Com o objetivo de oferecer um ponto de compara¸c˜ao entre os algoritmos dinˆamicos e

est´aticos, a Tabela 6.13 traz os resultados do seguinte experimento: para cada grafo dos

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 76

grupos Random4-n, Long-n e Square-n foi dado aos algoritmos de Prim [37] e Kruskal [33]

o mesmo tempo de CPU gasto pelo algoritmo RT(DRD+ST) para a realiza¸c˜ao de 20000

atualiza¸c˜oes nesses grafos. Assim, computou-se o n´umero de atualiza¸c˜oes processadas por

cada um desses algoritmos.

Tabela 6.13: Quantidade de atualiza¸c˜oes processadas pelos algoritmos cl´assicos para

AGMs utilizando mesmo tempo de CPU gasto pelo Algoritmo RT(DRD+ST).

Instˆancia n m Tempo RT(DRD+ST) Prim Kruskal

Random4-n.10.0 1024 4080 0,37 20000 581 1081

Random4-n.11.0 2048 8178 0,65 20000 440 946

Random4-n.12.0 4096 16372 1,22 20000 350 785

Random4-n.13.0 8192 32748 2,27 20000 290 692

Random4-n.14.0 16384 65524 4,51 20000 206 661

Random4-n.15.0 32768 131055 9,36 20000 161 642

Random4-n.16.0 65536 262122 19,22 20000 126 595

Random4-n.17.0 131072 524273 30,12 20000 75 423

Random4-n.18.0 262144 1048566 65,33 20000 59 388

Random4-n.19.0 524288 2097139 142,35 20000 50 326

Long-n.10.0 1024 2944 0,79 20000 1412 2553

Long-n.11.0 2048 5936 0,63 20000 510 881

Long-n.12.0 4096 11808 1,21 20000 494 798

Long-n.13.0 8192 23729 2,61 20000 442 810

Long-n.14.0 16384 47601 6,07 20000 444 887

Long-n.15.0 32768 95150 14,18 20000 408 969

Long-n.16.0 65536 190493 28,97 20000 352 878

Long-n.17.0 131072 380952 67,17 20000 339 925

Long-n.18.0 262144 761894 148,92 20000 304 863

Long-n.19.0 524288 1523343 321,90 20000 272 705

Square-n.10.0 1024 2964 0,62 20000 1117 1922

Square-n.11.0 2025 5938 1,04 20000 809 1534

Square-n.12.0 4096 12037 1,97 20000 664 1287

Square-n.13.0 8190 24283 2,50 20000 389 769

Square-n.14.0 16384 48742 4,68 20000 294 672

Square-n.15.0 32761 97634 9,71 20000 244 656

Square-n.16.0 65536 195768 18,97 20000 187 581

Square-n.17.0 131044 392136 37,97 20000 150 524

Square-n.18.0 262144 785034 77,83 20000 115 444

Square-n.19.0 524176 1570146 156,67 20000 91 343

Total 600000 11375 25540

M´edia 20000 379 851

Atrav´es da Tabela 6.13 pode-se concluir que a diferen¸ca entre os tempos de CPU apre-

sentados pelos algoritmos dinˆamicos em compara¸c˜ao com os algoritmos est´aticos ´e muito

grande. Com esta tabela, conclui-se ainda que a utiliza¸c˜ao de um bom algoritmo dinˆamico

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 77

´e fundamental para o desempenho de aplica¸c˜oes baseadas em entradas dinˆamicas, onde o

grafo passa por altera¸c˜oes estruturais ao longo da execu¸c˜ao da mesma.

Estes experimentos foram propostos com o intuito de avaliar o desempenho dos algoritmos

quando submetidos a seq

uˆencias de incrementos de custo em arestas da AGM. A justiﬁca-

tiva para a execu¸c˜ao de experimentos nesse ambiente ´e que buscas locais podem varrer um

determinado espa¸co de busca simplesmente alterando os custos de arestas. Para uma var-

redura objetiva, essas altera¸c˜oes s˜ao normalmente voltadas a incrementos ou decrementos

que forcem a altera¸c˜ao da AGM. Nessa se¸c˜ao optou-se por realizar apenas incrementos nos

custos de arestas da AGM, o que pode fazer com que essa AGM mude freq

uentemente.

As Tabelas 6.14 a 6.16, trazem os tempos de CPU gastos pelos algoritmos para execu-

tar uma seq

uˆencia de 20000 incrementos de custos no valor de n/16 em arestas da AGM.

Novamente, comprova-se o que vˆem sendo constatado pelos experimentos estruturados re-

alizados ao longo deste trabalho: RT(DRD) e RT(DRD+ST) s˜ao os melhores algoritmos para

tais circunstˆancias, nas quais o segundo algoritmo obt´em uma ligeira vantagem quando

aplicado em instˆancias contendo longos caminhos de v´ertices (representadas pelo conjunto

de instˆancias Long-n).

A se¸c˜ao 6.2.2 avaliou experimentalmente os algoritmos da Tabela 6.3 utilizando um con-

junto real de instˆancias, obtidas do The 2005/2006 Ninth DIMACS Implementation Chal-

lenge – Shortest Paths. Este conjunto de instˆancias foi escolhido por oferecer um conjunto

robusto e completo de grafos, composto de instˆancias aleat´orias e estruturadas, e ainda

por um conjunto de grafos sobre o mapa rodori´ario dos Estados Unidos da Am´erica.

Para tanto, foram executados experimentos aleat´orios (Se¸c˜ao 6.2.2.1) e estruturados

(Se¸c˜ao 6.2.2.2). Foi constatado que, tanto para os experimentos da Se¸c˜ao 6.2.2.1 quanto

para os experimentos da Se¸c˜ao 6.2.2.2, os algoritmos e estruturas de dados propostos

nessa disserta¸c˜ao obtiveram os menores tempos de CPU por execu¸c˜ao, destacando-se os

algoritmos RT(DRD) e RT(DRD+ST).

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 78

Tabela 6.14: Tempos de CPU (segundos) para as instˆancias Random4-n ap´os 20000 incrementos de valor n/16 em arestas da AGM.

Instˆancia n m C-Mod(DRD+ST) C(ET+ST) RT(Sort) RT(RD) RT(DRD) RT(ST) RT(ET+ST) RT(DRD+ST)

Random4-n.10.0 1024 4080 1,33 1,86 0,02 0,33 0,20 3,79 0,53 0,38

Random4-n.11.0 2048 8178 2,22 2,38 0,01 0,68 0,32 6,42 0,73 0,50

Random4-n.12.0 4096 16372 4,19 4,32 0,03 1,22 0,61 12,13 1,34 0,77

Random4-n.13.0 8192 32748 8,14 9,25 0,06 3,11 1,15 24,67 3,69 1,32

Random4-n.14.0 16384 65524 16,01 22,68 0,15 7,71 2,43 53,73 10,41 2,75

Random4-n.15.0 32768 131055 34,65 63,40 0,30 23,34 4,74 114,95 36,91 5,27

Random4-n.16.0 65536 262122 77,69 194,91 0,66 74,27 9,52 269,24 136,38 10,22

Random4-n.17.0 131072 524273 158,04 529,69 1,29 422,18 19,36 645,67 422,77 19,77

Random4-n.18.0 262144 1048566 317,46 1259,43 2,65 1426,46 38,77 1498,02 1152,66 39,21

Random4-n.19.0 524288 2097139 641,64 3135,93 5,30 4291,39 78,05 3384,15 2916,86 78,59

Tabela 6.15: Tempos de CPU (segundos) para as instˆancias Long-n ap´os 20000 incrementos de valor n/16 em arestas da AGM.

Instˆancia n m C-Mod(DRD+ST) C(ET+ST) RT(Sort) RT(RD) RT(DRD) RT(ST) RT(ET+ST) RT(DRD+ST)

Long-n.10.0 1024 2944 1,24 1,59 0,01 0,55 0,27 4,28 0,53 0,43

Long-n.11.0 2048 5936 2,17 2,92 0,01 1,41 0,50 7,01 0,71 0,63

Long-n.12.0 4096 11808 4,03 6,77 0,03 3,68 0,90 13,05 1,31 1,15

Long-n.13.0 8192 23729 7,87 16,58 0,06 29,92 1,84 26,52 3,59 1,91

Long-n.14.0 16384 47601 16,02 46,26 0,18 163,20 4,45 57,02 11,43 4,55

Long-n.15.0 32768 95150 38,50 130,22 0,34 702,38 9,65 136,02 38,93 10,29

Long-n.16.0 65536 190493 87,45 365,01 0,68 3273,62 20,60 319,19 122,40 20,83

Long-n.17.0 131072 380952 185,72 934,10 1,45 21227,40 44,19 746,52 353,95 45,64

Long-n.18.0 262144 761894 384,78 2304,84 3,05 - 97,76 1772,30 929,32 97,41

Long-n.19.0 524288 1523343 803,80 5198,41 6,36 - 207,67 - 2266,31 201,94

6.2 Algoritmos: Atualiza¸c˜ao de

Arvores Geradoras M´ınimas em Grafos Dinˆamicos 79

Tabela 6.16: Tempos de CPU (segundos) para as instˆancias Square-n ap´os 20000 incrementos de valor n/16 em arestas da AGM.

Instˆancia n m C-Mod(DRD+ST) C(ET+ST) RT(Sort) RT(RD) RT(DRD) RT(ST) RT(ET+ST) RT(DRD+ST)

Square-n.10.0 1024 2964 1,25 1,39 0,02 0,53 0,28 4,05 0,53 0,44

Square-n.11.0 2025 5938 2,17 2,60 0,02 0,95 0,41 6,69 0,67 0,65

Square-n.12.0 4096 12037 3,94 5,75 0,03 2,64 0,76 12,64 1,35 0,99

Square-n.13.0 8190 24283 7,68 14,21 0,06 14,03 1,50 25,09 3,52 1,71

Square-n.14.0 16384 48742 15,31 38,30 0,15 62,54 3,30 55,39 10,45 3,46

Square-n.15.0 32761 97634 33,92 112,97 0,32 228,26 6,55 128,99 36,53 6,81

Square-n.16.0 65536 195768 74,54 329,62 0,71 794,62 12,65 308,13 121,43 12,84

Square-n.17.0 131044 392136 146,44 867,67 1,34 4659,24 23,02 738,83 353,27 23,93

Square-n.18.0 262144 785034 285,00 2150,43 2,71 - 44,78 1751,10 929,67 45,36

Square-n.19.0 524176 1570146 564,65 - 6,01 - 88,55 - 2275,51 88,69

6.3 Resumo do Cap´ıtulo 80

Complementando os resultados estruturados e ainda aproveitando que este ´e o experi-

mento mais diﬁcil de se executar atrav´es de algoritmos dinˆamicos (i.e., para os algoritmos

dinˆamicos estas seq

uˆencias de atualiza¸c˜ao induzem aos casos mais dif´ıceis de serem tra-

tados), foi mostrada na Se¸c˜ao 6.2.2.3 a vantagem num´erica de se utilizar um algoritmo

dinˆamico ao inv´es de um algoritmo est´atico, com 52,75 e 23,5 vezes mais atualiza¸c˜oes

processadas que os algoritmos de Prim [37] e de Kruskal [33].

Na Se¸c˜ao 6.2.2.4 foi realizado um experimento composto apenas por incrementos em

arestas da AGM, com o objetivo de se gerar mudan¸cas estruturais nessa ´arvore. Nesse

caso, foi adotado o valor de atualiza¸c˜ao igual a n/16 e novamente os melhores algoritmos

foram RT(DRD) e RT(DRD+ST).

Embora os algoritmos do grupo C tenham se mostrado competitivos quando a seq

uˆen-

cia de atualiza¸c˜oes foi aleatoriamente gerada, este resultado n˜ao permaneceu assim quando

esta seq

uˆencia for¸cou mudan¸cas na AGM. Os tempos de CPU desses m´etodos se manti-

veram praticamente iguais para todos os experimentos com exce¸c˜ao do primeiro, o que

prova que tais algoritmos n˜ao s˜ao competitivos. Ainda assim, ﬁcou clara a contribui¸c˜ao

da estrutura para ´arvores dinˆamicas DRD-trees, proposta no Cap´ıtulo 4 desta disserta¸c˜ao.

Isto aconteceu porque tais algoritmos analisam uma grande quantidade de arestas com

respeito `a conectividade, justamente a grande contribui¸c˜ao dessa estrutura.

Este cap´ıtulo analisou experimentalmente os algoritmos e estruturas de dados propostos

nesta disserta¸c˜ao. Foi demonstrada a eﬁciˆencia da estrutura de dados para ´arvores di-

nˆamicas DRD-trees com rela¸c˜ao `a execu¸c˜ao da opera¸c˜ao de consulta sobre conectividade

entre dois v´ertices. Os algoritmos propostos para atualiza¸c˜ao da AGM de um grafo dinˆa-

mico quando submetido a uma altera¸c˜ao no custo de uma aresta tamb´em se mostraram

eﬁcientes, apresentando bons resultados nos principais experimentos realizados.

Esta disserta¸c˜ao abordou o problema de atualiza¸c˜ao da ´arvore geradora m´ınima de um

grafo sujeito a incrementos ou decrementos em custos de arestas.

Foram propostos algoritmos e estruturas de dados que, embora n˜ao tragam avan¸cos

do ponto de vista te´orico, conseguem aliar a facilidade de implementa¸c˜ao computacional

com um excelente desempenho pr´atico.

Este desempenho foi analisado atrav´es de trˆes classes de experimentos. A primeira

delas foi executada sobre as estruturas de dados para ´arvores dinˆamicas, mostrando que

as DRD-trees s˜ao estruturas r´apidas em consultas de conectividade e ao mesmo tempo

n˜ao apresentam grandes diferen¸cas nos tempos de CPU utilizados para a realiza¸c˜ao de

opera¸c˜oes de link e cut.

A segunda classe de experimentos consistiu em utilizar os mesmos parˆametros de

grafos e atualiza¸c˜oes apresentados em [10] para comparar os algoritmos aqui propostos

com aquele que obteve os melhores resultados naquele trabalho. Os resultados mostraram

que a utiliza¸c˜ao da estrutura de dados DRD-trees contribuiu para a redu¸c˜ao signiﬁcativa

dos tempos de CPU do algoritmo de Cattaneo et al. [10], bem como os algoritmos aqui

propostos obtiveram tempos computacionais menores que esses dois algoritmos em grande

parte dos experimentos desta classe.

A terceira e ´ultima classe de experimentos utilizou os grafos disponibilizados em [15]

para oferecer experimentos condizentes com aqueles encontrados no mundo real. Submeti-

dos a essas instˆancias, sob seq

uˆencias de atualiza¸c˜oes aleat´orias, estruturadas e unit´arias,

os algoritmos propostos neste trabalho continuaram obtendo os melhores tempos de CPU

quando comparados aos algoritmos de [10].

Cabe destacar os algoritmos RT(DRD+ST) e RT(DRD) como os melhores algoritmos para

a grande maioria dos experimentos aqui utilizados.

7 Conclus˜oes e Trabalhos Futuros 82

As implementa¸c˜oes dos algoritmos e estruturas de dados aqui propostos foram con-

duzidas com o cuidado de se prover c´odigos reus´aveis e eﬁcientes, baseados na linguagem

de programa¸c˜ao C++ e no projeto orientado a objetos. Desta forma, um c´odigo bas-

tante ﬂex´ıvel ´e ent˜ao, a partir de agora, disponibilizado ao dom´ınio p´ublico sob a licen¸ca

GPL. Salienta-se que nenhum algoritmo foi implementado beneﬁciando-se de bibliotecas

de c´odigo fechado.

Este trabalho pode ser estendido atrav´es da implementa¸c˜ao eﬁciente dos algoritmos de

Holm et al. [30, 31] e de Frederickson [17, 18], que, embora tenham apresentado resultados

pr´aticos ruins, s˜ao importantes devido `as suas complexidades te´oricas. O trabalho de

Cattaneo et al. [10] j´a experimentou ambas as implementa¸c˜oes acima e constatou sua

ineﬁciˆencia pr´atica. Contudo, essa implementa¸c˜ao foi baseada na biblioteca LEDA [34]

(Library of Eﬃcient Data-types and Algorithms), uma biblioteca de c´odigo fechado e

comercial. A implementa¸c˜ao aberta desses algoritmos permitiria sua compara¸c˜ao com

os algoritmos aqui propostos, principalmente nos experimentos k-Clique em [10], onde o

algoritmo C(ET+ST) n˜ao foi experimentado por ser ineﬁciente.

[1] Acar, U., Blelloch, G., Harper, R., Vittes, J., Woo, S. Dynamizing static

algorithms, with applications to dynamic trees and history dependence. Em Pro-

ceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (New Orleans,

2004), p. 524–533.

[2] Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M. Minimizing dia-

meters of dynamic trees. Em Proceedings of the 24th International Colloquium on

Automata, Languages, and Programming (Bologna, 1997), P. Degano, R. Gorrieri,

e A. Marchetti-Spaccamela, Eds., vol. 1256 de Lecture Notes in Computer Science,

Springer-Verlag, p. 270–280.

[3] Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M. Maintaining di-

ameter, center, and median of fully-dynamic trees with top-trees, 2003. Referˆencia

on-line em http://arxiv.org/abs/cs/0310065, visitada em 15 de janeiro de 2006.

[4] Amato, G., Cattaneo, G., Italiano, G. Experimental analysis of dynamic

minimum spanning tree algorithms (extended abstract). Em Proceedings of the 8th

Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, 1997), p. 314–

323.

[5] Bent, S., Sleator, D., Tarjan, R. Biased search trees. SIAM Journal on

Computing 14 (1985), 545–568.

[6] Buriol, L. Roteamento do Tr´afego na Internet: Algoritmos para Projeto e Opera-

¸c˜ao de Redes com Protocolo OSPF. Tese de Doutorado, Universidade Estadual de

Campinas, 2003.

[7] Buriol, L., Resende, M., Ribeiro, C., Thorup, M. A memetic algorithm for

OSPF routing. Em Proceedings of the 6th INFORMS Telecom (Boca Raton, 2002),

p. 187–188.

[8] Buriol, L., Resende, M., Ribeiro, C., Thorup, M. A hybrid genetic algorithm

for the weight setting problem in OSPF/IS-IS routing. Networks 46 (2005), 36–56.

[9] Buriol, L., Resende, M., Thorup, M. Speeding up shortest path algorithms.

Relat´orio T´ecnico TD-5RJ8B, AT&T Labs Research, 2003.

[10] Cattaneo, G., Faruolo, P., Petrillo, U., Italiano, G. Maintaining dyna-

mic minimum spanning trees: An experimental study. Em Algorithm Engineering

and Experiments: 4th International Workshop (San Francicsco, 2002), D. Mount e

C. Stein, Eds., vol. 2409 de Lecture Notes in Computer Science, Springer-Verlag,

p. 111–125.

Referˆencias 84

[11] Chin, F., Houck, D. Algorithms for updating minimal spanning trees. Journal of

Computer and System Sciences 16 (1978), 333–344.

[12] Cormen, T., Leiserson, C., Rivest, R., Stein, C. Introduction to Algorithms,

2nd ed. MIT Press, 2001.

[13] Das, B., Loui, M. Reconstructing a minimum spanning tree after deletion of any

node. Algorithmica 31 (2001), 530–547.

[14] Demetrescu, C., Goldberg, A., Johnson, D. Ninth DI-

MACS implementation challenge, 2006. Referˆencia on-line em

http://www.dis.uniroma1.it/~challenge9/, visitada em 23 de junho de

2006.

[15] DIMACS. DIMACS implementation challenges. Referˆencia on-line em

http://dimacs.rutgers.edu/Challenges/, visitada em 23 de junho de 2006.

[16] Eppstein, D., Galil, Z., Italiano, G. F., Nissemzweig, A. Sparsiﬁcation – A

technique for speeding up dynamic graph algorithms. Journal of the ACM 44 (1997),

669–696.

[17] Frederickson, G. Data structures for on-line updating of minimum spanning

trees, with applications. SIAM Journal on Computing 14 (1985), 781–798.

[18] Frederickson, G. Ambivalent data structures for dynamic 2-edge-connectivity

and k smallest spanning trees. Em Proceedings of the 32nd Annual Symposium on

Foundations of Computer Science (San Juan, 1991), p. 632–641.

[19] Fredman, M., Tarjan, R. Fibonacci heaps and their use in improved network

optimization algorithms. Journal of the ACM 34 (1987), 596–615.

[20] Galil, Z., Italiano, G. Data structures and algorithms for disjoint set union

problems. ACM Computing Surveys 23 (1991), 319–244.

[21] Galil, Z., Italiano, G. Fully-dynamic algorithms for 2-edge connectivity. SIAM

Journal on Computing 21 (1992), 1047–1069.

[22] Harary, F. Graph Theory. Addison-Wesley, 1969.

[23] Held, M., Karp, R. The traveling-salesman problem and minimum spanning trees.

Operations Research 18 (1970), 1138–1162.

[24] Held, M., Karp, R. The traveling-salesman problem and minimum spanning trees:

Part II. Mathematical Programming 1 (1970), 6–25.

[25] Henzinger, M., King, V. Randomized dynamic graph algorithms with polyloga-

rithmic time per operation. Em Proceedings of the 27th ACM Symposium on Theory

of Computing (Las Vegas, 1995), p. 519–527.

[26] Henzinger, M., King, V. Maintaining minimum spanning trees in dynamic

graphs. Em Proceedings of the 24th International Colloquium on Automata, Lan-

guages, and Programming (Bologna, 1997), P. Degano, R. Gorrieri, e A. Marchetti-

Spaccamela, Eds., vol. 1256 de Lecture Notes in Computer Science, Springer-Verlag,

p. 594–604.

Referˆencias 85

[27] Henzinger, M., King, V. Randomized fully-dynamic graph algorithms with poly-

logarithmic time per operation. Journal of the ACM 46 (1999), 502–516.

[28] Henzinger, M., Poutr

e, H. Certiﬁcates and fast algorithms for biconnectivity in

fully dynamic graphs. Em Proceedings of the 3rd European Symposium on Algorithms

(Corfu, 1995), P. Spirakis, Ed., vol. 959 de Lecture Notes in Computer Science,

Springer-Verlag, p. 594–604.

[29] Henzinger, M., Thorup, M. Sampling to provide or to bound: With applications

to fully dynamic graph algorithms. Random Structures and Algorithms 11 (1996),

171–184.

[30] Holm, J., de Lichtenberg, K. Top-trees and dynamic graph algorithms. Disser-

ta¸c˜ao de Mestrado, University of Copenhagen, 1998.

[31] Holm, J., de Lichtenberg, K., Thorup, M. Poly-logarithmic deterministic

fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and bi-

connectivity. Em Proceedings of the 30th ACM Symposium on Theory of Computing

(Dallas, 1998), p. 79–89.

[32] Karger, D., Klein, P., Tarjan, R. A randomized linear-time algorithm to ﬁnd

minimum spanning trees. Journal of the ACM 42 (1995), 321–328.

[33] Kruskal, J. On the shortest spanning subtree of a graph and the traveling salesman

problem. Proceedings of the American Mathematical Society 7 (1956), 48–50.

[34] Mehlhorn, K., N

aher, S. LEDA, a platform for combinatorial and geometric

computing. Communications of the ACM 38 (1995), 96–102.

[35] Miller, G., Reif, J. Parallel tree contraction and its application. Em Procee-

dings of the 26th Annual Symposium on Foundations of Computer Science (Portland,

1985), p. 478–489.

[36] Petrillo, U. Algorithm Engineering: Methodologies and Support Tools. Tese de

Doutorado, Universit´a di Salerno, 2001.

[37] Prim, R. Shortest connection networks and some generalizations. Bell Systems

Technical Journal 36 (1957), 1389–1401.

[38] Rauch, M. Fully Dynamic Graph Algorithms and Their Data Structures. Tese de

Doutorado, Princeton University, 1992.

[39] Rauch, M. Improved data structures for fully dynamic biconnectivity. Em Pro-

ceedings of the 26th ACM Symposium on Theory of Computing (Montreal, 1994),

p. 503–538.

[40] Rauch, M. Fully-dynamic biconnectivity in graphs. Algorithmica 13 (1995), 503–

538.

[41] Sleator, D., Tarjan, R. A data structure for dynamic trees. Journal of Computer

and System Sciences 26 (1983), 362–391.

Referˆencias 86

[42] Sleator, D., Tarjan, R. Self-adjusting binary trees. Em Proceedings of the 15th

ACM Symposium on Theory of Computing (Boston, 1983), p. 235–245.

[43] Sleator, D., Tarjan, R. Self-adjusting binary search trees. Journal of the ACM

32 (1985), 652–686.

[44] Spira, P., Pan, A. On ﬁnding and up dating spanning trees and shortest paths.

SIAM Journal on Computing 4 (1975), 375–380.

[45] Tarjan, R. Depth-ﬁrst and linear graph algorithms. SIAM Journal on Computing

1 (1972), 146–160.

[46] Tarjan, R. Eﬃciency of a good but not linear set union algorithm. Journal of the

ACM 22 (1975), 215–225.

[47] Werneck, R., Tarjan, R. Self-adjusting top trees. Em Proceedings of the 16th

Annual ACM-SIAM Symposium on Discrete Algorithms (Vancouver, 2005), p. 813–

822.

[48] Zaroliagis, C. Implementations and experimental studies of dynamic graph algo-

rithms. Em Experimental Algoritms - From Algorithm Design to Robust and Eﬃcient

Software, R. Fleischer, B. Moret, e E. Schmidt, Eds., vol. 2547 de Lecture Notes in

Computer Science. Springer-Verlag, 2002, p. 229–278.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 