Problema da árvore geradora de comunicação ótima: variantes, complexidade e aproximação (2016)
- Authors:
- Autor USP: RAVELO, SANTIAGO VALDES - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: OTIMIZAÇÃO COMBINATÓRIA
- Agências de fomento:
- Language: Português
- Abstract: O problema da árvore geradora de comunicação ótima recebe um grafo com comprimentos não negativos nas arestas e um requerimento não negativo entre cada par de vértices; sendo o objetivo encontrar uma árvore geradora do grafo que minimize o custo de comunicação, que é a soma sobre cada par de vértice da distância entre eles na árvore vezes o requerimento entre eles. Este problema é NP-difícil, assim como vários casos particulares dele. Neste trabalho estudamos algumas variantes deste problema, introduzimos novos casos particulares que são também NP-difíceis e propomos esquemas de aproximação polinomial para alguns deles.
- Imprenta:
- Data da defesa: 18.02.2016
-
ABNT
RAVELO, Santiago Valdés. Problema da árvore geradora de comunicação ótima: variantes, complexidade e aproximação. 2016. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2016. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12042016-145246/. Acesso em: 12 jun. 2024. -
APA
Ravelo, S. V. (2016). Problema da árvore geradora de comunicação ótima: variantes, complexidade e aproximação (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12042016-145246/ -
NLM
Ravelo SV. Problema da árvore geradora de comunicação ótima: variantes, complexidade e aproximação [Internet]. 2016 ;[citado 2024 jun. 12 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12042016-145246/ -
Vancouver
Ravelo SV. Problema da árvore geradora de comunicação ótima: variantes, complexidade e aproximação [Internet]. 2016 ;[citado 2024 jun. 12 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12042016-145246/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
