S-caminhos.

• Processo: 06/54065-2
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de julho de 2006
• Data de Término da vigência: 31 de dezembro de 2006
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: José Coelho de Pina Junior
• Beneficiário: Marcio Takashi Iura Oshiro
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Palavra(s)-Chave do Pesquisador: Emparelhamentos | Relacoes Min-Max | T-Caminhos

Resumo

Neste projeto de iniciação científica pretendemos estudar a teoria e algoritmos relacionados ao problema de encontrar uma coleção máxima de S-caminhos disjuntos. A fórmula min-max de Mader para este problema tem como conseqüências as fórmulas de Menger para o número máximo de RS-caminhos disjuntos, de Tutte-Berge para o número máximo de arestas em um emparelhamento e de Gallai para o número máximo de T-caminhos disjuntos. Acreditamos que este tópico é rico o suficiente para que ao final do projeto o estudante tenha adquirido bastante familiaridade com algumas das técnicas mais fundamentais em otimização combinatória para um possível futuro mestrado na área. (AU)