Estudo experimental de aproxima��es para o problema de Steiner
--------------------------------------------------------------

Aluno: Michel Vale Ferreira <michelvf@uol.com.br>

Neste trabalho, planejamos implementar de tr�s a quatro algoritmos
de aproxima��o para o problema de Steiner em grafos e fazer um 
estudo comparativo da sua performance em inst�ncias aleat�rias e
em inst�ncias das bibliotecas encontradas em 
http://ganley.org/steiner/related.html.

Os algoritmos que pretendemos implementar aparecem descritos em 
pseudoc�digo na disserta��o de Gondo [1]. S�o eles o algoritmo de
Zelikovsky (cap 2), o algoritmo do ganho relativo (cap 4), o algoritmo
de Robin e Zelikovsky (cap 6) e, se houver tempo, o algoritmo do
pr�-processamento, de Karpinsky e Zelikovsky (cap 5).

Esses algoritmos n�o s�o muito complicados. Eles s�o variantes uns
dos outros e usam v�rias rotinas em comum, assim nos parece vi�vel 
implementar v�rios deles e compar�-los experimentalmente no per�odo 
de tempo dispon�vel. Ser� interessante observar o comportamento 
destes algoritmos na pr�tica frente ao que dizem suas an�lises
te�ricas. 

Cronograma
----------
         (a)    (b)     (c)      (d)      (e)        (f)       (g)
tarefa  maio   junho   julho   agosto   setembro   outubro   novembro 
   1     x      
   2     x       x       x       x
   3                             x         x          x
   4                                                  x         x

Tarefas: 
1. estudo dos conceitos b�sicos.
2. implementa��o dos algoritmos.
3. testes e compara��es dos algoritmos.
4. escrita do trabalho.

(a) Estudo da nota��o e do problema (cap 1) e implementa��o dos 
    algoritmos de Dijkstra e Kruskal.
(b) Estudo e implementa��o do algoritmo de Zelikovsky. 
(c) Estudo e implementa��o dos algoritmos do ganho relativo e de Robin 
    e Zelikovsky. 
(d) T�rmino das implementa��es e testes comparativos com inst�ncias
    aleat�rias. 
(e) testes comparativos com inst�ncias da biblioteca http://ganley.org/steiner/related.html.
(f) t�rmino dos estudos comparativos e in�cio da escrita do trabalho.
(g) finaliza��o da escrita do trabalho.

Refer�ncias

[1] E.K. Gondo, �rvores k-Restritas e Aproxima��es para �rvores de
Steiner, Disserta��o de Mestrado, IME-USP 2002.