Optimal Communication Spanning Tree (2021)
- Authors:
- Autor USP: CHOQUE, JAINOR NESTOR CARDENAS - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2021.tde-10032022-204719
- Subjects: PROGRAMAÇÃO LINEAR; PROGRAMAÇÃO INTEIRA E FLUXOS EM REDE; PROGRAMAÇÃO MATEMÁTICA; PROGRAMAÇÃO MISTA
- Keywords: Árvore geradora; Árvore Geradora de Comunicação Ótima; Árvore GomoryHu; Branch-and-cut; Programação linear inteira
- Agências de fomento:
- Language: Inglês
- Abstract: Neste trabalho estudamos o problema da Árvore Geradora de Comunicação Ótima (AGCO). Uma instância deste problema consiste de uma quádrupla (G, c, R, w) composta por um grafo conexo G = (V, E), uma função não-negativa c que atribui a cada elemento e E um custo c(e), um conjunto R de pares de vértices em V , e uma função não-negativa w, chamada demanda, definida sobre R. Cada par (u, v) de R é chamado um requisito, o vértice u é chamado origem e o vértice v é chamado destino do par. Para uma dada árvore geradora T de G, o custo de comunicação de um requisito r = (u, v) é definido como a demanda w(r) multiplicada pela distância entre u e v em T (sendo a distância a soma dos custos das arestas no caminho de u a v em T). No problema da Árvore Geradora de Comunicação Ótima, dada uma instância (G, c, R, w), o objetivo é encontrar em G uma árvore geradora que minimiza a soma total dos custos de comunicação de todos os requisitos em R. Este problema foi introduzido por T. C. Hu em 1974 e é sabido ser NP-difícil. Alguns de seus casos especiais, não tão triviais, podem ser resolvidos em tempo polinomial. Investigamos aqui dois tais casos especiais do problema AGCO, ambos para o caso de G ser um grafo completo. No primeiro deles, todas as arestas do grafo têm o mesmo custo. Neste caso, a solução é dada pela árvore de Gomory-Hu de uma certa rede associada à instância dada. No segundo problema, todos os requisitos têm a mesma demanda, e a solução é dada por uma árvore que é uma estrela.Também estudamos algumas formulações lineares inteiras mistas para o problema AGCO. Para isso, estudamos formulações lineares para o problema da árvore geradora mínima, algumas das quais fazem uso de fluxos. Tais formulações são combinadas e dão origem a algumas formulações mistas para o problema AGCO. Implementamos algoritmos branchand-cut para tais formulações, e apresentamos os resultados computacionais obtidos
- Imprenta:
- Data da defesa: 08.07.2021
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
CHOQUE, Jainor Nestor Cardenas. Optimal Communication Spanning Tree. 2021. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2021. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-10032022-204719/. Acesso em: 03 out. 2024. -
APA
Choque, J. N. C. (2021). Optimal Communication Spanning Tree (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-10032022-204719/ -
NLM
Choque JNC. Optimal Communication Spanning Tree [Internet]. 2021 ;[citado 2024 out. 03 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-10032022-204719/ -
Vancouver
Choque JNC. Optimal Communication Spanning Tree [Internet]. 2021 ;[citado 2024 out. 03 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-10032022-204719/
Informações sobre o DOI: 10.11606/D.45.2021.tde-10032022-204719 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
