Approximation algorithms for cut problems in graphs

Abstract

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)