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

Abstract

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.