Return to search

Algorithms for the directed k-spanner with minimum degree steiner tree problem

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

Identiferoai:union.ndltd.org:IBICT/oai:192.168.11:11:ri/13146
Date08 October 2013
CreatorsBraga, Hugo Vinícius Vaz
ContributorsSilva, Flávio Morais de Assis
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Sourcereponame:Repositório Institucional da UFBA, instname:Universidade Federal da Bahia, instacron:UFBA
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0021 seconds