Busca avançada
Ano de início
Entree

Algoritmos de aproximação para problemas de Corte em Grafos

Processo: 19/24866-3
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de janeiro de 2020
Vigência (Término): 31 de dezembro de 2020
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Mário César San Felice
Beneficiário:Esther Calderan Hoffmann
Instituição-sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
Assunto(s):Algoritmos de aproximação   Otimização combinatória   Programação linear inteira   Grafos   Análise de algoritmos

Resumo

Nos problemas de corte em grafos busca-se encontrar um conjunto de arestas que, ao serem removidas, desconectam determinados vértices, cumprindo requisitos e particularidades dos mais diversos cenários. Esses problemas são bastante relevantes tanto do ponto de vista de dificuldade teórica, muito deles sendo problemas NP-difíceis para os quais diversos algoritmos de aproximação são conhecidos, quanto pela motivação de aplicações práticas por modelarem problemas de computação distribuída, identificação de vulnerabilidades em redes e agrupamento de dados.Este projeto tem como objetivos o estudo de algoritmos de aproximação para problemas de corte em grafos, como o Multiway Cut e o Multicut, a implementação e testes de alguns destes algoritmos, além da produção de um relatório técnico com os principais resultados estudados.Esta iniciação científica também visa introduzir a candidata à área de pesquisa científica e objetiva complementar sua formação na área de Ciência da Computação, aprofundando seu conhecimento em otimização combinatória, algoritmos de aproximação e técnicas de projeto e análise de algoritmos. (AU)