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

• Processo: 11/08033-0
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de agosto de 2011
• Data de Término da vigência: 29 de fevereiro de 2016
• Área de 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
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | caminhos disjuntos nas arestas | conjectura de Gallai | decomposição em caminhos | grafos | partição do conjunto das arestas de um grafo em caminhos | Teoria dos Grafos e Algoritmos

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

(7)

(As publicações científicas contidas nesta página são originárias da Web of Science ou da SciELO, cujos autores mencionaram números dos processos FAPESP concedidos a Pesquisadores Responsáveis e Beneficiários, sejam ou não autores das publicações. Sua coleta é automática e realizada diretamente naquelas bases bibliométricas)

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. (13/20733-2, 13/03447-6, 13/11431-2, 11/08033-0, 14/01460-8)

BOTLER, F.; TALON, A.. . DISCRETE MATHEMATICS, v. 340, n. 9, p. 2275-2285, SEP 2017. (13/03447-6, 11/08033-0, 14/01460-8)

BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y.. . EUROPEAN JOURNAL OF COMBINATORICS, v. 66, p. 28-36, DEC 2017. (13/03447-6, 13/11431-2, 11/08033-0, 14/01460-8, 13/20733-2)

BOTLER, FABIO; JIMENEZ, ANDREA. . DISCRETE MATHEMATICS, v. 340, n. 6, p. 1405-1411, JUN 2017. (13/03447-6, 11/08033-0, 14/01460-8)

BOTLER, F.; MOTA, G. O.; WAKABAYASHI, Y.. . DISCRETE MATHEMATICS, v. 338, n. 11, p. 1845-1855, NOV 6 2015. (11/08033-0, 13/11431-2, 14/01460-8, 13/20733-2)

BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y.. . JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 122, p. 508-542, JAN 2017. (13/20733-2, 13/03447-6, 13/11431-2, 11/08033-0, 14/01460-8)

BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y.. . DISCRETE APPLIED MATHEMATICS, v. 245, p. 11-pg., 2018-08-20. (11/08033-0, 13/11431-2, 13/20733-2, 13/03447-6, 14/01460-8)

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 (IME/SBI) São Paulo.