Advanced search
Start date
Betweenand

Approximation algorithms for cut problems in graphs

Grant number: 19/24866-3
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): January 01, 2020
Effective date (End): December 31, 2020
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Mário César San Felice
Grantee:Esther Calderan Hoffmann
Home Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil

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)