Busca avançada
Ano de início
Entree

Problemas de particionamento em grafos

Processo: 15/11930-4
Linha de fomento:Bolsas no Exterior - Estágio de Pesquisa - Doutorado
Vigência (Início): 01 de setembro de 2015
Vigência (Término): 31 de agosto de 2016
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Yoshiko Wakabayashi
Beneficiário:Phablo Fernando Soares Moura
Supervisor no Exterior: Stephan Thomasse
Instituição-sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
Local de pesquisa : École Normale Supérieure, Lyon (ENS), França  
Vinculado à bolsa:13/19179-0 - Problemas de otimização sobre partição em grafos, BP.DR

Resumo

O foco desta proposta de pesquisa é o estudo de problemas de particionamento em grafos. Estamos particularmente interessados nos problemas de orientação própria, cobertura por caminhos e recoloração convexa. No primeiro problema, devemos orientar todas as arestas de um grafo de tal forma que os graus de entrada dos vértices nessa orientação induzam um particionamento do conjunto de vértices em uma quantidade mínima de conjuntos estáveis. No segundo problema, estamos interessados em encontrar uma partição do conjunto de vértices de um grafo em um número mínimo de caminhos. Finalmente, no problema de recoloração convexa, temos que particionar o conjunto de vértices do grafo de tal forma que cada elemento da partição induza um subgrafo conexo do grafo de entrada. (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.
COELHO, RAFAEL S.; MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. The k-hop connected dominating set problem: approximation and hardness. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 34, n. 4, p. 1060-1083, NOV 2017. Citações Web of Science: 1.
CAMPELO, MANOEL; MOURA, PHABLO F. S.; SANTOS, MARCIO C. Lifted, projected and subgraph-induced inequalities for the representatives k-fold coloring polytope. DISCRETE OPTIMIZATION, v. 21, p. 131-156, AUG 2016. 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.