ETC – Encontro de Teoria da Computação
O Encontro de Teoria da Computação (ETC) é um fórum voltado para a grande área de Teoria da Computação, sendo proposto por membros da Comissão Especial em Algoritmos, Combinatória e Otimização (CE-ACO) da Sociedade Brasileira de Computação, com objetivo de promover uma maior divulgação da área para a comunidade brasileira de computação e afins. O ETC acontece dentro do Congresso da Sociedade Brasileira de Computação (CSBC), evento itinerante, a cada ano acontece em uma cidade do Brasil, para dessa forma atingir todas as regiões e possibilitar a participação.
Este evento é voltado para os alunos em formação, mas também visando proporcionar uma maior integração entre os pesquisadores e profissionais que atuam na mesma, seja com enfoque em teoria pura ou em aplicações, estimulando a discussão da importância dos fundamentos da computação e sua aplicação direta no entendimento e resolução de problemas das mais diversas áreas e segmentos de mercado.
Primeiro lugar: “PTAS para problema do empacotamento soma mínima com quadrados”
Autores: Rachel Vanucchi Saraiva (Unicamp), Rafael Schouery (Unicamp).
Segundo lugar: “Complexidade Parametrizada do problema de reconfiguração de separadores”
Autores: Guilherme de Castro Mendes Gomes (UFMG), Vinícius dos Santos (UFMG).
Terceiro lugar: “On total coloring of small fullerene nanodiscs”
Autores: Mariana Cruz (UFRJ), Celina Figueiredo (UFRJ), Diana Sasaki (UFRJ), Diane Castonguay (UFG).
Trabalhos Premiados
Primeiro Lugar: Título: Minimum Density of Identifying Codes of Hexagonal Grids with a Finite Number of Rows
Autores: Rudini Sampaio (UFC – Brasil), Gabriel A. G. Sobral (USP – Brasil), Yoshiko Wakabayashi (USP – Brasil)
Menções honrosas
Título: Emparelhamento Conexo Ponderado é NP-completo
Autores: Guilherme de C. M. Gomes (UFMG – Brasil), Bruno P. Masquio (UERJ – Brasil), Paulo Pinto (UERJ – Brasil), Vinicius dos Santos (UFMG – Brasil), Jayme L. Szwarcfiter (UERJ / UFRJ – Brasil)
Título: Instances for the Maximum Clique Problem with Hardness Guarantees Autores: Victor Campos (UFC – Brasil), Renato Carmo (UFPR – Brasil), Rodrigo Nogueira (UFC – Brasil)
Trabalhos Premiados:
Primeiro lugar: Título: Spanning Cover Inequalities for the Capacitated Vehicle Routing Problem
Autores: Guilherme Arcencio, Matheus Mattioli, Pedro Hokama, Mário César San Felice
Segundo lugar: Título: Lower Bounds for the Partial Grundy Number of the Lexicographic Product of Graphs
Autores: Kenny Domingues, Yuri Oliveira, Ana Silva
Terceiro lugar: Título: Some Partial Results on Linial’s Conjecture for Matching-Spine Digraphs
Autores: Jadder Cruz, Cândida Silva, Orlando Lee
Trabalhos Premiados:
Primeiro lugar: Decomposition of (2k+1)-regular graphs containing special spanning 2k-regular Cayley graphs into paths of length 2k+1.
Autores: Fábio Botler (UFRJ), Luiz Hoffmann (UFRJ)
Segundo lugar: The odd chromatic index of almost all graphs.
Autores: Fábio Botler (UFRJ), Lucas Colucci (Central European University), Yoshiharu Kohayakawa (USP)
Terceiro lugar: Conjuntos Dominantes e Dominantes Independentes em Grafos de Petersen Generalizados.
Autores: Alessandra Pereira (UNICAMP), Christiane N. Campos (UNICAMP)
Anais link: https://sol.sbc.org.br/index.php/etc/issue/view/578
Trabalhos Premiados:
Primeiro lugar:
Título: A Constant-Factor Approximation for the Generalized Cable-Trench Problem
Autores: Marcelo Benedito (Unicamp – Brasil), Lehilton Pedrosa (Unicamp – Brasil), Hugo Rosado (Unicamp – Brasil)
Segundo lugar:
Título: Equitable Partition of Graphs into Independent Sets and Cliques
Autores: Bruno Monteiro (UFMG – Brasil), Vinicius dos Santos (UFMG – Brasil)
Terceiro lugar:
Título: A proof for Berge’s Dual Conjecture for Bipartite Digraphs
Autores: Caroline Silva (UFSCar – Brasil), Cândida Silva (UFSCar – Brasil), Orlando Lee (UNICAMP – Brasil)
Anais link: https://sol.sbc.org.br/index.php/etc/issue/view/385
Trabalhos Premiados:
Primeiro lugar:
Título: alpha-Diperfect digraphs
Autores: Maycon Sambinelli (UNICAMP – Brazil),Cândida Silva (UFSCAR – Brazil), Orlando Lee (UNICAMP – Brazil)
Menção honrosa
Título: Online Circle and Sphere Packing
Autores: Carla Lintzmayer (UFABC – Brazil), Flavio Miyazawa (UNICAMP – Brazil), Eduardo Xavier (UNICAMP – Brazil)
Anais link: https://sol.sbc.org.br/index.php/etc/issue/view/193
Trabalhos Premiados:
Primeiro lugar:
Título: Número de Ramsey relativo a arestas de potências de caminhos
Autores: Dennis Clemens (TUHH – Germany), Matthew Jenssen (London School of Economics – UK), Yoshiharu Kohayakawa (USP – Brasil), Natasha Morrison (Oxford – UK), Guilherme Mota (USP – Brasil), Damian Reding (TUHH – Germany), Barnaby Roberts (London School of Economics – UK)
Segundo lugar:
Título: Método exato para um problema de alocação justa
Autores: Edênis F. Azevedo (IME-USP – Brasil), Carlos E. Ferreira (IME-USP – Brasil), Alexandre S. Freire (EACH-USP – Brasil), Aritanan Gruber (UFABC – Brasil), Augusto Vellozo (Tecsinapse -Brasil)
Terceiro lugar:
Título: Advances in anti-Ramsey theory for random graphs
Autor: Guilherme O. Mota (USP – Brazil)
Anais link: https://sol.sbc.org.br/index.php/etc/issue/view/194
Trabalho Premiado:
Título: Some families of 0-rotatable graceful caterpillars
Autores: Atílio Luiz (UNICAMP – Brasil), Christiane Campos (UNICAMP-Brasil), Bruce Richter (University of Waterloo – Canada)
Anais link: https://sol.sbc.org.br/index.php/etc/issue/view/512