Texto completo
| |
| Autor(es): |
Diego Silva Cintra
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | São Carlos. |
| Instituição: | Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) |
| Data de defesa: | 2019-08-08 |
| Membros da banca: |
Maria Cristina Ferreira de Oliveira;
Jesús Pascual Mena Chalco;
Danilo Medeiros Eler;
Rosane Minghim
|
| Orientador: | Maria Cristina Ferreira de Oliveira |
| Resumo | |
O paradigma multinível tem sido utilizado na resolução de problemas de otimização combinatória em grafos. Ele opera gerando uma hierarquia de grafos contraídos e resolvendo o problema em uma versão reduzida do grafo original, o que reduz o espaço de soluções e permite utilizar um algoritmo cujo tempo de execução seria inviável no grafo original. Recentemente, foi proposto um arcabouço multinível flexível para a solução de problemas em grafos bipartidos, o qual admite vários parâmetros de entrada. Essa dissertação apresenta uma nova metáfora visual que auxilia na interpretação do resultado de executar o paradigma multinível em um grafo bipartido e na avaliação do impacto de diferentes escolhas dos parâmetros nos resultados. O objetivo é ilustrar como a nova metáfora associada ao paradigma multinível apoia tarefas analíticas em grafos bipartidos. Para validar este objetivo um sistema foi desenvolvido como prova de conceito, denominado MObViewer, que além da nova metáfora visual utiliza visualizações adicionais para auxiliar nas tarefas analíticas. Dois tipos de estudos de caso foram conduzidos para validar o MObViewer. O primeiro considera questões analíticas sobre o paradigma multinível elaboradas em conjunto com um especialista, e respondidas considerando grafos sintéticos, construídos em um ambiente controlado. Já o segundo consiste em uma investigação exploratória sobre grafos bipartidos que modelam dados do mundo real. Os resultados mostram que a nova metáfora visual auxilia a identificação do impacto da alteração dos parâmetros de entrada do paradigma multinível e ilustram como a integração entre visualização e o arcabouço multinível pode apoiar a visualização exploratória de grafos bipartidos. (AU) | |
| Processo FAPESP: | 16/25107-0 - Visualização de grandes grafos apoiada pelo paradigma multinível e aglomeração de arestas |
| Beneficiário: | Diego Silva Cintra |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |