Algoritmos para conexidade em grafos dinâmicos (2024)
- Authors:
- Autor USP: RODRIGUES, ARTHUR HENRIQUE DIAS - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2024.tde-14052025-111528
- Subjects: ALGORITMOS; ANÁLISE DE ALGORITMOS; TEORIA DOS GRAFOS
- Keywords: Conexidade; Connectivity; Dynamic graphs; Euler tour trees; Floresta maximal de peso mínimo; Grafos dinâmicos; Minimum spanning forest
- Language: Português
- Abstract: Essa dissertação aborda os problemas de conexidade em grafos dinâmicos e floresta maximal de peso mínimo em grafos planos ponderados dinâmicos. Para o primeiro problema é apresentado a solução proposta por Holm, de Lichtenberg e Thorup junto às estruturas de dados utilizadas e a elaboração de um algoritmo que resolve esse problema restrito a floresta dinâmicas. Para o segundo problema é apresentada de forma didática a solução de Eppstein et al. Por fim é apresentado um limitante inferior por operação para os problemas estudados
- Imprenta:
- Data da defesa: 22.11.2024
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
ABNT
RODRIGUES, Arthur Henrique Dias. Algoritmos para conexidade em grafos dinâmicos. 2024. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2024. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-14052025-111528/. Acesso em: 23 jan. 2026. -
APA
Rodrigues, A. H. D. (2024). Algoritmos para conexidade em grafos dinâmicos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-14052025-111528/ -
NLM
Rodrigues AHD. Algoritmos para conexidade em grafos dinâmicos [Internet]. 2024 ;[citado 2026 jan. 23 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-14052025-111528/ -
Vancouver
Rodrigues AHD. Algoritmos para conexidade em grafos dinâmicos [Internet]. 2024 ;[citado 2026 jan. 23 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-14052025-111528/
Informações sobre o DOI: 10.11606/D.45.2024.tde-14052025-111528 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
