Defesa de Dissertação de Mestrado de Carlos Thadeu Duarte Santos, em 06/03/2024, às 09:00 horas, na sala 310 do Instituto de Computação e por videoconferência
Link para defesa: meet.google.com/fbu-sqnu-aao
Determinação do Índice de Extensão de Grafos Através de Algoritmos Paralelos e Heurísticos
Resumo:
O problema de t-admissibilidade apresenta um desafio min-max, visando determinar se um grafo G possui uma árvore geradora T onde a distância entre quaisquer dois vértices adjacentes em G é no máximo t em T. O índice de extensão de G, s (G), é o menor t para o qual G é t-admissível. Este problema encontra-se na classe P para t ≤ 2, NP-completo para s (G) ≤ t, t ≥ 4, e permanece aberto para t=3 desde 1995.
Couto et al. (2022) desenvolveram algoritmos de força bruta sequenciais e paralelos para construção de árvore geradora. Além disso, os mesmos autores apresentaram duas heurísticas gulosas para gerar árvores de soluções candidatas. Nestas abordagens, vértices são selecionados em cada etapa para fazerem parte da árvore dadas medidas locais ou globais quanto aos graus. Contudo como pode haver empates nessa escolha induzindo índices distintos no final, foi deixado em aberto uma análise detalhada sobre o critério de desempate.
Nesta dissertação, apresentamos sete novas heurísticas utilizando o conceito de importância de vértice em redes complexas. Nossa avaliação abrange vários tipos de grafos, incluindo Barabási-Albert, Erdős-Rényi, Watts-Strogatz e grafos bipartidos. Adicionalmente, apresentamos um novo algoritmo de força bruta paralelo empregando um método baseado em ciclos induzidos no grafo, comparando seu desempenho com algoritmos propostos anteriormente. Comparamos nossas estratégias propostas (paralelas e heurísticas) com abordagens existentes, alcançando os resultados mais promissores até o momento para valores precisos (ou heurísticas) do índice de extensão.
Abstract:
The t-admissibility problem presents a min-max challenge, aiming to determine if a graph G has a spanning tree T where the distance between any two adjacent vertices in G is at most t in T. The stretch index of G, s (G), is the smallest t for which G is t-admissible. This problem is in class P for t ≤ 2, NP-complete for s (G) ≤ t, $t ≥ 4, and remains open for t=3 since 1995.
Couto et al. (2022) developed sequential and parallel brute force algorithms for spanning tree construction. Additionally, the same authors presented two greedy heuristics for generating candidate solution trees. In these approaches, vertices are selected at each step to be part of the tree given local or global measures regarding the degrees. However, as ties may occur in this selection, inducing different indices in the end, a detailed analysis on the tie-breaking criterion was left open.
In this dissertation, we introduce seven new heuristics utilizing the concept of vertex importance in complex networks. Our evaluation spans various graphs types, including Barabási-Albert, Erdős-Rényi, Watts-Strogatz, and bipartite graphs. Additionally, we present a new parallel brute-force algorithm employing a method based on induced cycles in the graph, comparing its performance with previously proposed algorithms. We compare our proposed strategies (parallel and heuristic) with existing approaches, achieving the most promising results to date for precise values (or heuristics) of the stretch index.
Banca examinadora:
Prof. Luís Felipe Ignácio Cunha, UFF – Presidente
Prof. Leandro Santiago de Araújo, UFF
Prof. Igor Machado Coelho, UFF
Prof. Daniel Fábio Domingues Posner, UFRRJ