Busca avançada
Ano de início
Entree

Decomposição de um grafo em caminhos: aspectos estruturais e algorítmicos

Processo: 11/08033-0
Linha de fomento:Bolsas no Brasil - Doutorado
Vigência (Início): 01 de agosto de 2011
Vigência (Término): 29 de fevereiro 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:Fábio Happ Botler
Instituição-sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
Bolsa(s) vinculada(s):14/01460-8 - Decomposições de grafos, BE.EP.DR
Assunto(s):Algoritmos de aproximação   Grafos

Resumo

Investigaremos neste projeto um problema clássico da teoria dos grafos sobre partição do conjunto das arestas de um grafo em um número mínimo de caminhos. Este problema tem suas raízes numa conjectura de Gallai (1966) sobre uma cota superior para esse número, que só depende do número de vértices do grafo. Esta conjectura afirma que o conjunto das arestas de um grafo conexo com n vértices pode ser decomposto em no máximo (n+1)/2 caminhos. A literatura a respeito desta conjectura é relativamente pequena: sabe-se que ela foi estabelecida para o caso em que o grafo só tem vértices de grau ímpar e para o caso em que os vértices de grau par induzem um subgrafo com uma estrutura bem especial. Temos interesse em investigar a validade dessa conjectura para outras classes de grafos e também explorar aspectos algorítmicos deste problema. Resultados algorítmicos sobre este problema não foram encontrados na literatura.

Publicações científicas (6)
(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)
BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y. Decomposing highly connected graphs into paths of length five. DISCRETE APPLIED MATHEMATICS, v. 245, n. SI, p. 128-138, AUG 20 2018. Citações Web of Science: 1.
BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y. Decomposing regular graphs with prescribed girth into paths of given length. EUROPEAN JOURNAL OF COMBINATORICS, v. 66, p. 28-36, DEC 2017. Citações Web of Science: 0.
BOTLER, F.; TALON, A. Decomposing 8-regular graphs into paths of length 4. DISCRETE MATHEMATICS, v. 340, n. 9, p. 2275-2285, SEP 2017. Citações Web of Science: 1.
BOTLER, FABIO; JIMENEZ, ANDREA. On path decompositions of 2k-regular graphs. DISCRETE MATHEMATICS, v. 340, n. 6, p. 1405-1411, JUN 2017. Citações Web of Science: 5.
BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y. Decomposing highly edge-connected graphs into paths of any given length. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 122, p. 508-542, JAN 2017. Citações Web of Science: 7.
BOTLER, F.; MOTA, G. O.; WAKABAYASHI, Y. Decompositions of triangle-free 5-regular graphs into paths of length five. DISCRETE MATHEMATICS, v. 338, n. 11, p. 1845-1855, NOV 6 2015. Citações Web of Science: 4.
Publicações acadêmicas
(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)
BOTLER, Fábio Happ. Decomposição de grafos em caminhos. 2016. Tese de Doutorado - Universidade de São Paulo (USP). Instituto de Matemática e Estatística São Paulo.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.