Clique aqui e inclua na sua agenda
Dia 04/12, 10h30, Sala 2016
Palestrante: Victor Campos (UFC)
Título: Novas dualidades tipo Menger para digrafos com aplicações ao problema de linkage meio inteiro
Resumo:
Apresentamos novas relações min-max em digrafos entre o número máximo de caminhos que satisfaz algumas propriedades e a ordem de cortes correspondentes. Definimos estes objetos para capturar as propriedades essenciais de conexão de um conjunto de terminais a uma estrutura fortemente conectada como um bramble ou um gride cilíndrico, ferramenta utilizada em soluções do problema de linkage meio inteiro. Esta estratégia tem sido utilizada em múltiplos resultados, normalmente com demonstrações longas e técnicas, e nosso objetivo é apresentar abstrações para serem utilizadas de uma forma simples e unificada. Apresentamos duas demonstrações para as relações min-max, uma mais simples mostrando como representar os problemas por interseção e união de matroides e uma outra que gera algoritmos melhores transformando os problemas numa aplicação do Teorema de Menger em digrafos auxiliares. Como aplicação dos nossos resultados, mostramos como simplificar e melhorar alguns resultados de Edwards et al. [ESA 2017] e de Giannopoulou et al. [SODA 2022] sobre como achar linkages meio inteiros. Relativo ao resultado de Edwards et al. [ESA 2017], além de mais simples, nossa demonstração apresenta um limitante quase ótimo para a conectividade forte de um digrafo que garante a existência de um linkade meio inteiro para qualquer conjunto de terminais quando o digrafo tem um bramble de ordem grande (de forma equivalente, que tem largura em árvore direcionada grande, que é o caso mais difícil das demonstrações). Relativo ao resultado de Giannopoulou et al. [SODA 2022], nossa demonstração é mais simples e utiliza brambles ao invés de grides cilíndricos para roteamento. Além de mostrar o mesmo tipo de roteamento com uma estrutura mais fraca, esta mudança oferece melhores limitantes para o tamanho da largura em árvore direcionada necessária para a sua aplicação. Esperamos que as estruturas apresentadas sejam aplicáveis a mais problemas de roteamento em digrafos por serem, na opinião dos coautores, simples, robustas e versáteis.
Este trabalho foi realizado em coautoria com Jonas Costa, Raul Lopes e Ignasi Sau.
