Busca avançada
Ano de início
Entree

Problemas de particionamento em grafos

Processo: 15/11930-4
Modalidade de apoio: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: 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
Assunto(s):Grafos   Teoria dos grafos
Palavra(s)-Chave do Pesquisador:coloração de vértices | orientação de arestas | particionamento de grafos | particionamento em caminhos | Teoria dos Grafos e Otimização

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)

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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)
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, . (13/03447-6, 15/11930-4, 13/19179-0)
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, . (15/11930-4, 16/21250-3, 17/22611-2, 13/19179-0)
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, . (13/03447-6, 15/11930-4, 13/19179-0)

Por favor, reporte erros na lista de publicações científicas utilizando este formulário.