Sala dos Tachos
DIA 1: 17/11 (terça-feira)
SALA 1 (Sala dos Tachos)
09:00 – 09:20 – Abertura
9:20 – 10:10 – Palestra: Um passeio aleatório polinomial numa árvore de algoritmos, Prof. Edson Norberto Cáceres (UFMS, Brasil).
10:10 – 11:50 – Sessão Técnica I
|
SALA ETC 01 (Sala dos Tachos) – Temática: Grafos 1 |
SALA ETC 02 (Sala dos Tachos) – Temática: Otimização 1 |
| Characterizing Networks Admitting k Arc-disjoint Branching Flows
Cláudio Carvalho (UFC), Jonas Costa (UFC), Raul Lopes (UFC), Ana Karolina Maia (UFC), Nicolas Nisse (INRIA-CNRS), Cláudia Linhares Sales (UFC) |
O Problema do Brigadista com Vértices Resistentes
Luis Filipe de Lima Sales (IFCE), Raimundo Azevedo Neto (IFCE), Glauber Ferreira Cintra (IFCE) |
| Decomposition of (2k+1)-regular graphs containing special spanning 2k-regular Cayley graphs into paths of length 2k+1
Fábio Botler (UFRJ), Luiz Hoffmann (UFRJ) |
Formulação de fluxo em arcos para problemas de agrupamento capacitado
Vítor Gomes Chagas (UNICAMP), Manuel Iori (UNIMORE) |
| Emparelhamentos Conexos
Bruno P. Masquio (UERJ), Paulo E. D. Pinto (UERJ), Jayme L. Szwarcfiter |
Modelos Pseudo Polinomiais para o Problema do Empacotamento Colorido
Yulle G. F. Borges (UNICAMP), Rafael C. S. Schouery (UNICAMP) |
| On Embedding Trees in Grids
Vitor Tocci Ferreira de Luca, Fabiano de Souza Oliveira, Jayme Luiz Szwarcfiter (UERJ, UFRJ) |
12:00 – 14:00 – Intervalo do Almoço
14:00 – 16:15 – SECOMU
16:15 – 16:30 – Intervalo com Patrocinadores
SALA 1 (Sala dos Tachos)
16:30 – 17:20 – Palestra: Heavy independent sets and spanning arborescences with many leaves, Profa. Cristina Gomes Fernandes (USP, Brasil).
17:20 – 19:00 – Sessão Técnica II
|
SALA ETC 01 (Sala dos Tachos) – Temática: Grafos 2 |
SALA ETC 02 (Sala dos Tachos) – Temática: Grafos 3 |
| A complexidade do reconhecimento de grafos k-fino próprio de precedência
Flavia Bonomo-Braberman (UBA, Argentina), Fabiano Oliveira (UERJ), Moysés Sampaio Jr. (UFRJ), Jayme Szwarcfiter (UERJ, UFRJ) |
Linial’s Dual Conjecture for Path-Spine Digraphs
Vinícius de Souza Carvalho (UFSCAR), Cândida Nunes da Silva (UFSCAR), Orlando Lee (UNICAMP) |
| Proper Orientations of Chordal Graphs
Julio Araujo (UFC), Alexandre Cezar (UFC), Carlos Vinícius Gomes Costa Lima (UFC), Vinicius Fernandes dos Santos (UFMG), Ana Shirley Ferreira Silva (UFC) |
(Star, k)-colourings of graphs with bounded treewidth
C. A. Weffort-Santos (UNICAMP), L. L. C. Pedrosa (UNICAMP) |
| Particularidades do Problema de Partição na Convexidade P3 em Grafos com Treewidth Limitada
Lorrana F. de Castro (UFF), Rodolfo A. de Oliveira (UFF), Fábio Protti (UFF) |
The odd chromatic index of almost all graphs
Fábio Botler (UFRJ), Lucas Colucci, Yoshiharu Kohayakawa (USP) |
| Um Limitante Superior para o Número Geodésico nos Grafos de Kneser
João V. S. Leite (UFF), Marcos Bedo (UFF), Rodolfo A. de Oliveira (UFF) |
DIA 2: 18/11 (quarta-feira)
Sala 1 (Sala dos Tachos)
Palestras transmitidas simultaneamente no canal da SBC no YouTube
09:00 – 10:00 – Palestra: Algoritmos Exatos para Roteamento de Veículos: avanços e desafios, Prof. Eduardo Uchoa Barboza (UFF, Brasil)
10:00 – 11:00 – Palestra: Aplicações de Roteamento e Alocação: da Universidade para a Sociedade, Profa. Luciana Salete Buriol (UFRGS, Brasil)
11:00 – 12:00 – Palestra: A beleza e o poder da Complexidade Computacional: possibilidades, desafios, impactos sociais e seus trilhões de dólares, Profa. Rosiane de Freitas Rodrigues (UFAM, Brasil)
12:00 – 14:00 – Intervalo do Almoço
14:00 – 16:15 – SECOMU
16:15 – 16:30 – Intervalo com Patrocinadores
16:30 – 17:45 – Sessão Técnica III
|
SALA ETC 01 (Sala dos Tachos) – Temática: Grafos 4 |
SALA ETC 02 (Sala dos Tachos) – Temática: Otimização 2 |
| A result on total coloring of circulant graphs
Mauro N. Alves Junior (UERJ), Diana Sasaki (UERJ) |
Um modelo estendido para o problema de roteamento em anéis de dois níveis
Cecília Lescano Osório (UFMS), Edna Ayako Hoshino (UFMS) |
| Número de Grundy impróprio de subclasses de cografos
Efraim Rodrigues (UFC), Cláudia Linhares Sales (UFC) |
Valid Inequalities for the Green Vehicle Routing Problem
Matheus Diógenes Andrade (UNICAMP), Fábio Luiz Usberti (UNICAMP) |
| The Rainbow Connection Number of Triangular Snake Graphs
Aleffer Rocha (UTFPR), Sheila M. Almeida (UTFPR), Leandro M. Zatesko (UTFPR) |
Propriedades do Problema da Floresta Geradora k-Rotulada
Pedro Jorge de Abreu Figueredo (UFC), Manoel Campêlo (UFC) |
17:45 – 19:00 – Sessão Técnica IV
|
SALA ETC 01 (Sala dos Tachos) – Temática: Grafos 5 |
SALA ETC 02 (Sala dos Tachos) – Temática: Aplicações |
| Problemas de M-partição em cografos
Raquel Souza Francisco Bravo (UFF), Maria Luíza López Cruz (UFF) |
Sobre a decomposição de um transdutor bidirecional finitamente valorado
Rodrigo de Souza (UFRPE) |
| A new sufficient condition for the existence of 3-kernels
Alonso Ali (UNICAMP), Orlando Lee (UNICAMP) |
Meta-Heurísticas para Geração Automática de Sistemas Corretores de Erros Baseados em Codificação Convolucional
Lucas F. Muniz (UFABC), Carla N. Lintzmayer (UFABC), Denis G. Fantinato (UFABC) |
| Conjuntos Dominantes e Dominantes Independentes em Grafos de Petersen Generalizados
A. A. Pereira (UNICAMP), C. N. Campos (UNICAMP) |
Application of data mining and complex networks in the representation of purchasing associations: a case study in supermarket purchases
Maicon Lima (UFG), Melque Henrique Castro (UFG), Thiago Leite (UFG), Douglas Cordeiro (UFG), Nubia Rosa da Silva (UFG) |
19:00 – Encerramento.
DIA 3: 19/11 (quinta-feira)
19:00 – 19:00 – Premiação dos melhores artigos: no Palco (6) e Praça (5) do #Espaço40Graus no Ambiente 3D do CSBC 2020.
RESUMOS DAS PALESTRAS
Palestra 1:
Um passeio aleatório polinomial numa árvore de algoritmos
Palestrante: Prof. Edson Norberto Cáceres (UFMS, Brasil)
Resumo:
Faremos um passeio aleatório, finito, nos diferentes tipos de algoritmos para resolver problemas complexos, tais como Algoritmos determinísticos, Algoritmos de Aproximação, Algoritmos Aleatórios, Algoritmos FPT, Meta Heurísticas e Computação Quântica. Além disso, abordaremos como o computador impactou o desenvolvimento de algoritmos e algumas das novas tendências na solução de problemas com o uso do computador.
Palestra 2:
Heavy independent sets and spanning arborecences with many leaves
Palestrante: Profa. Cristina Gomes Fernandes (USP, Brasil)
Resumo:
The MaxLeaves problem consists of, given a rooted directed graph, finding a spanning arborecence with as many leaves as possible. In this talk, we will show a surprising relation between MaxLeaves on rooted directed acyclic graphs and the problem of finding a maximum weight independent set (wMIS) on claw free graphs. From this relation, we will derive a new 3/2-approximation for MaxLeaves on rooted directed acyclic graphs. This is joint work with Carla N. Lintzmayer.
Palestra 3:
Algoritmos Exatos para Roteamento de Veículos: avanços e desafios
Palestrante: Prof. Eduardo Uchoa Barboza (UFF, Brasil)
Resumo:
O Problema de Roteamento de Veículos (VRP na sigla em inglês) é um dos mais estudados na área de otimização, tendo aplicação direta na redução de custos e de emissões de CO2 na logística de distribuição de bens e serviços. Existem centenas de variantes do VRP, correspondendo as diferentes características dos sistemas de logística reais. Todas essas variantes pertencem à classe NP-difícil e a grande maioria dos algoritmos usados na prática para o VRP são heurísticas. Entretanto, uma série de avanços obtidos nos últimos anos nos chamados algoritmos de branch-cut-and-price para o VRP possibilitaram que problemas de tamanho razoável, da ordem de 200 clientes, possam hoje ser resolvidos de forma ótima em tempo razoável. Também será apresentado o VRPSolver, um software recentemente criado que implementa um algoritmo de branch-cut-and-price avançado para um modelo geral de VRP e que pode ser customizado (utilizando uma interface em linguagem Julia) para a maioria das variantes conhecidas.
Transmitida simultaneamente no canal da SBC no YouTube
Palestra 4:
Aplicações de Roteamento e Alocação: da Universidade para a Sociedade
Palestrante: Profa. Luciana Salete Buriol (UFRGS, Brasil)
Resumo:
Diariamente resolvemos problemas de roteamento e alocação nas nossas tarefas quotidianas. O mesmo acontece com instituições que, muitas vezes, sem saber da complexidade dos problemas, oferecem soluções distantes da otimalidade, sem saber que resolver tais problemas demandam conhecimento específico. Esta situação em geral só é percebida quando tais problemas já não são mais pequenos, e soluções não automatizadas são insatisfatórias. Nesta palestra eu pretendo descrever três casos reais de problemas que envolvem roteamento e alocação que estão sendo trabalhados em conjunto com alunos de pós-graduação e instituições de Porto Alegre. Um problema se refere ao roteamento de veículos para a entrega de produtos por uma empresa. Outro sobre a alocação de médicos plantonistas no Hospital de Clínicas de Porto Alegre. O terceiro problema trata da logística do atendimento medico domiciliar, incluindo alocação e roteamento, unindo conhecimento dos dois primeiros problemas. Na palestra eu vou detalhar, além das aplicações e as técnicas usadas para resolvê-las, o caminho trilhado para que houvesse produção científica e tecnológica.
Transmitida simultaneamente no canal da SBC no YouTube
Palestra 5:
A beleza e o poder da Complexidade Computacional: possibilidades, desafios, impactos sociais e seus trilhões de dólares
Palestrante: Profa. Rosiane de Freitas (UFAM, Brasil)
Resumo:
Nestes tempos de pandemia da COVID-19, onde a disseminação exponencial do contágio pelo vírus Sars-Cov-2, seguida da proliferação exponencial deste vírus dentro do corpo humano, foram matéria jornalística para o grande público e o entendimento de sistemas complexos ganhou reforço, bem como o gancho para o entendimento de aspectos da complexidade computacional em si. Nesta palestra, deste modo, o fascinante mundo da complexidade computacional será explorado, com uma visão geral sobre a teoria relacionada, principais resultados, modelos teóricos de máquinas e problemas, problemas fáceis x difíceis e aqueles ainda em aberto, como os clássicos de isomorfismo em grafos e o Open8 de escalonamento com restrições de precedência. Estratégias algorítmicas determinísticas de otimização combinatória e baseadas em inteligência computacional serão brevemente revisadas. Exemplos de aplicações em bioinformática, ambientais, na web, telecomunicações, na logística de cadeias produtivas, no desenvolvimento de software e na indústria de entretenimento, serão fornecidos. Por fim, os impactos sociais desta teoria que possibilita e fomenta trilhões de dólares pelo mundo tecnológico e financeiro serão discutidos. What a wonderful e-Complex world!!
Transmitida simultaneamente no canal da SBC no YouTube