Aspectos algorítmicos e estruturais de problemas de Cobertura e Empacotamento em grafos

Resumo

Este é o projeto de pesquisa de pós-doutorado de Phablo F. S. Moura, a ser desenvolvido sob a supervisão do professor Flávio K. Miyazawa, no Instituto de Computação da Universidade Estadual de Campinas (UNICAMP). O projeto se insere nas áreas de algoritmos e teoria dos grafos, e tem como foco o estudo de problemas de cobertura e empacotamento em grafos. Neste projeto, pretendemos investigar os seguintes problemas.O primeiro consiste em particionar (ou seja, cobrir e empacotar) o conjunto de vértices de um grafo de tal forma que cada parte induza um subgrafo conexo e, além disso, as partes sejam balanceadas, ou seja, o peso da parte mais leve é maximizado.No segundo problema, estamos interessados em cobrir o conjunto de vértices de um grafo usando o menor número possível de caminhos. Esse é uma generalização do clássico problema do caminho Hamiltoniano.O terceiro problema apresentado neste projeto é relacionado à uma conjectura que trata de encontrar condições suficientes para que todo grafo direcionado contenha, como subgrafo, alguma subdivisão de um dado grafo direcionado. (AU)