Busca avançada
Ano de início
Entree

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

Processo: 16/21250-3
Linha de fomento:Bolsas no Brasil - Pós-Doutorado
Vigência (Início): 01 de abril de 2017
Vigência (Término): 31 de março de 2020
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Convênio/Acordo: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Pesquisador responsável:Flávio Keidi Miyazawa
Beneficiário:Phablo Fernando Soares Moura
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Bolsa(s) vinculada(s):17/22611-2 - Aspectos algorítmicos e estruturais de problemas de Cobertura e Empacotamento em grafos, BE.EP.PD
Assunto(s):Algoritmos de aproximação   Teoria dos 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)

Publicações científicas
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
ABOULKER, PIERRE; COHEN, NATHANN; HAVET, FREDERIC; LOCHET, WILLIAM; MOURA, PHABLO F. S.; THOMASSE, STEPHAN. Subdivisions in digraphs of large out-degree or large dichromatic number. ELECTRONIC JOURNAL OF COMBINATORICS, v. 26, n. 3 JUL 19 2019. Citações Web of Science: 0.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.
Mapa da distribuição dos acessos desta página
Para ver o sumário de acessos desta página, clique aqui.