Submitted by LIVIA FREITAS (livia.freitas@ufba.br) on 2013-10-08T15:47:13Z
No. of bitstreams: 1
Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5) / Approved for entry into archive by LIVIA FREITAS(livia.freitas@ufba.br) on 2013-10-08T15:47:22Z (GMT) No. of bitstreams: 1
Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5) / Made available in DSpace on 2013-10-08T15:47:22Z (GMT). No. of bitstreams: 1
Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5) / Arvores Steiner são comumente utilizadas para modelar restrições na execução da operação
de multicast. Nesta dissertação nós tratamos um novo problema denominado árvore
Steiner com Grau Mínimo e fator de dilatação k em Grafos Direcionados (cujo acrônimo
em inglês é DSMDStP). Este problema consiste em: dado um grafo direcionado G(V,E),
um n´o origem s ∈ V , um fator de dilatação k (k ∈ R+, k ≥ 1) e um conjunto de terminais
T ⊆ V \ {s}, encontrar uma arborescência onde o custo entre o nó de origem s
em G e cada t ∈ T é menor ou igual a k vezes o custo da menor distância entre este
par de nós, ao passo que o grau máximo de saída é minimizado. DSMDStP não admite
aproximação sublogarítmica (a menos que NP ⊂ DTIME(nlog log n). Nós descrevemos
um algoritmo de aproximação que gera uma arborescência com grau máximo de saída
limitado por 2q|T| + 2 + O(log |T|) · d∗, onde d∗ consiste no grau máximo da solução
ótima e a arborescência é uma spanner com fator de dilatação (a partir da raiz) de
k ·1 + maxt2T {dist(s,t,G)}mint2T dist(s,t,G)}, onde dist(s, t,G) representa o caminho de menor custo entre s e t em G. Embora nosso fator de dilata¸c˜ao viole k, nos experimentos, a restrição de spanner foi satisfeita ou, em média, quase satisfeita. Além disso, o grau de saída medido
nos experimentos foi baixo. Nós também descrevemos uma heurística que garante um
fator de dilatação de k · (⌊q|T|⌋ + 2), mas não limita o grau máximo de saída. Nos
experimentos, a heurística mostrou-se extensível com relação ao grau máximo, além de sempre superar os outros algoritmos nesta métrica. A heurística gerou, adicionalmente,
uma spanner com fator de violaçãao baixo. / Salvador
| Identifer | oai:union.ndltd.org:IBICT/oai:192.168.11:11:ri/13146 |
| Date | 08 October 2013 |
| Creators | Braga, Hugo Vinícius Vaz |
| Contributors | Silva, Flávio Morais de Assis |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFBA, instname:Universidade Federal da Bahia, instacron:UFBA |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds