ETC - 11º Encontro de Teoria da Computação
Sobre o Evento
O ETC é um fórum voltado para a grande área de Teoria da Computação, proposto por membros da Comissão Especial em Algoritmos, Combinatória e Otimização (CE-ACO), com objetivo de promover uma maior divulgação da área para a comunidade brasileira de computação e afins, através do principal evento da SBC, o CSBC.
Esse evento é voltado primeiramente para alunos em formação, mas também visa proporcionar uma maior integração entre os pesquisadores e profissionais que atuam na área, 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.
Em sua décima primeira edição, convidamos a comunidade a compartilhar resultados de pesquisa por meio da submissão de resumos estendidos, abrangendo tanto pesquisas em nível de pós-graduação como também iniciação científica na graduação e também a prestigiar os trabalhos selecionados com sua presença nas apresentações. O evento é aberto para a comunidade, com especial interesse nos alunos em formação de graduação e de pós-graduação.
Programação do Evento
Terça-feira (21/07)
Quarta-feira (22/07)
Quinta-feira (23/07)
Detalhes da Programação
Sessão 1 - Chair: Celina Miraglia Herrera de Figueiredo
Lista de Trabalhos
- 08h40 – 09h00 | Coloração Total de Grafos Linha de Grafos Completos
- Giovana Badreddine, Hebert Coelho da Silva, Márcia R. Cappelle
- 09h00 – 09h20 | On r-dynamic coloring of graphs in subclasses of planar and circulant graphs
- Juan Gutierrez, Grover Ugarte
- 09h20 – 09h40 | On the (2,1)-total number of indifference graphs
- M. M. Omai, Atílio Gomes Luiz, C. N. Campos
- 09h40 – 10h00 | On Rainbow Coloring of Quadrilateral Snake Graphs
- Felipe Bertoluci Wendt, Aleffer Rocha, M. M. Omai
- 10h00 – 10h20 | Coloração de identificação local em grafos split-comparabilidade
- Robson Medrado de Oliveira, Márcia R. Cappelle, Hebert Coelho da Silva, Julliano Rosa Nascimento
- 10h20 – 10h40 | p−Role Assignment for Cayley Graph Hℓ,p
- Athos José de Araújo, Paulo Felipe Candia Cazon, André da Cunha Ribeiro
- 10h40 – 11h00 | Atribuição de papéis sob restrições núcleo–periferia em produto corona de grafos
- Jarlilson Guajajara, Diane Castonguay, Julliano Rosa Nascimento
- 11h00 – 11h20 | Rotulação de arestas semiforte em grafos com grau máximo elevado
- Luis Gustavo da Soledade Gonzaga, C. N. Campos
- 11h20 – 11h40 | Jogo da Cobertura de Vértices em Grafos
- Josefran Bastos, Fabricio Siqueira Benevides, Thiago Marcilon, Nicolas Martins, Nicolas Nisse, Rudini Menezes Sampaio
Sessão 2 - Chair: Lehilton Pedrosa
Lista de Trabalhos
- 16h50 – 17h10 | Escalonamento de Tarefas com Níveis Variados de Criticidade
- Elisa DellArriva, Flavio K. Miyazawa
- 17h10 – 17h30 | Minimum k-labeled triangle forest: complexity and greedy approximations
- Santiago Ravelo, Cristina G. Fernandes
- 17h30 – 17h50 | Uma Aproximação FPT Linear para o Problema da Cobertura Mínima por Varredura
- Lucas de Oliveira Silva, Lehilton Lelis Chaves Pedrosa
- 17h50 – 18h10 | Cobertura Exata por Caminhos Arco-Írirs com Conflitos em Grafos Tricoloridos
- Gustavo Souza, Santiago Ravelo
- 18h10 – 18h30 | On the conformability of the disjoint union of graphs
- Luerbio Faria, Mauro Nigro, Myriam Preissmann, Diana Sasaki
Sessão 3 - Chair: Márcia Cappelle
Lista de Trabalhos
- 8h30 – 8h50 | Hardness results on parity subdivisions in digraphs
- Philipe Serra, Ana Karolinna Maia de Oliveira, Cibele Matos Freire
- 8h50 – 9h10 | Complexity of the Girth Problem on Arc-colored Digraphs
- Manoel Campelo, Rafael de Paiva Lima Filho, Claudia Linhares Sales
- 9h10 – 9h30| Aspectos Algorítmicos de Imersões em Digrafos
- Luis Antonio Lopes Bezerra, Ana Karolinna Maia de Oliveira, Jonas Costa
- 9h30 – 9h50 | NP-Completeness of Independent Locating-Dominating Sets in Planar Bipartite and Subcubic Graphs
- Dayllon Vinícius Xavier Lemos, Márcia R. Cappelle, Erika M. M. Coelho, Leslie Foulds, Humberto Longo
Sessão 4 - Chair: Vinícius Fernandes dos Santos
Lista de Trabalhos
- 16h – 16h20 | Set graphs are not definable in MSO1
- Bruno Bandeira Monteiro, Márcia Rosana Cerioli, Petrucio Viana
- 16h20 – 16h40 | A faster and adaptive partition function for Quicksort
- Victor Almeida Campos, Israel Mendes, Rodrigo Nogueira, Wladimir Araújo Tavares
- 16h40 – 17h | Arredondamento Aleatorizado para o Problema de Localização de Instalações Justo
- Jovânio José Galvão Júnior, Lehilton Lelis Chaves Pedrosa
- 17h – 17h20 | Lower Bounds on the Convergence to Nash Equilibrium in the Bin Packing Game
- André Vignatti, Flavio K. Miyazawa
- 17h20 – 17h40 | Filling more gaps on the edge coloring problem of split graphs
- Fernanda Vieira Dias Couto, Diego Ferraz, Celina M. H. Figueiredo, Sulamita Klein
- 17h40 – 18h | Caracterizando facetas do politopo do Subgrafo Gerador Balanceado Máximo via comutação
- Natália Coelho, Manoel Campelo
- 18h – 18h20 | Orthogonality between acyclic subdigraphs and paths in digraphs
- Caroline Ap. P. Silva, Cândida Nunes da Silva, Orlando Lee
- 18h20 – 18h40 | An Exact Framework for the Trigger Arc Traveling Salesman Problem
- Miguel Alessandro Miní Huambachano, Lucas de Oliveira Silva, Flavio K. Miyazawa
Sessão 5 - Chair: Rafael de Santiago
Lista de Trabalhos
- 9h20 – 9h40 | Jogo Normal Partizan de Dominação nas Estrelas
- Edileudo Maciel Filho, Jefter Maciel Paz, Rudini Menezes Sampaio, João Marcos Brito
- 9h40 – 10h | Espectro do número de intervalo na convexidade
- Álvaro Farias, Ana Karolinna Maia, Nalbert da Costa
- 10h – 10h20 | Autenticação Baseada em Tokens e Provas de Conhecimento Zero
- Yasmin Criôlo, Ruy José Guerra Barretto de Queiroz
- 10h20 – 10h40 | Ajuste Dinâmico de Tempos Semafóricos usando Previsão de Tráfego e Controle Fuzzy Sequencial
- Erick Lucas, Manoel Henrique de Oliveira Camargo, Maria José Pereira Dantas
- 10h40 – 11h | Mixed Integer Linear Programming Model for the Super-Colored Path Problem in Digraphs
- Rafael Marian, Wesly Carmesini Ataide, Rafael de Santiago, Álvaro Junio Pereira Franco
- 11h – 11h20 | Distance-k Domination in Triangular Matchstick Graphs and Triangulated Rectangular Grids
- Juan Gutierrez, Jorge Neira
- 11h20 – 11h40 | Cobrindo as arestas de cactos com caminhos
- Samuel Santos Morais, Ana Karolinna Maia, Carlos Vinícius Gomes Costa Lima
Sessão 6 - Chair: André Vignatti
Lista de Trabalhos
- 16h – 16h20 | An Approximation Algorithm for the Rich-Club Coefficient via Sample Complexity
- Eric Fukuyama, Leandro Miranda Zatesko, Murilo V. G. da Silva
- 16h20 – 16h40 | A Concentration Inequality for Multiple Estimators Based on a Polynomial-Time Computable Metric
- Vinícius Maurício Ribeiro, André Vignatti
- 16h40 – 17h | Análise assintótica e empírica de filas de prioridade avançadas aplicadas ao Algoritmo de Dijkstra
- Ana Carla de Araújo Fernandes, Lucas Castro, Thailsson de Andrade, Rosiane de Freitas
- 17h – 17h20 | A Clustering-Based Max-SAT Formulation for the Capacitated Vehicle Routing Problem with Time Windows
- Pedro Ferreira, Denilson Cordeiro, Rafael Dantas, Carlos Araújo, Alexandre Arruda
- 17h20 – 17h40 | Algoritmo para Alinhamento de Sequências em Grafos de Sequências com Economia de Espaço
- Thayná Gimenez, Eloi Araujo, Said Sadique Adi, Lucas Barbosa Rocha
- 17h40 – 18h | ALNS com Simulated Annealing e Shortest Path Heuristic para o Problema da Árvore de Steiner Clusterizada
- João Guilherme Guimarães e Silva, Alexandre Ribeiro
- 18h – 18h20 | Placement of charging stations for energy-constrained robots in spider graphs
- Lucas Cardoso Pereira, Santiago Ravelo
Tópicos de Interesse
Os tópicos de interesse incluem, mas não são limitados a:
- Algoritmos: análise e projeto de algoritmos, algoritmos exatos, algoritmos de aproximação, algoritmos probabilísticos, algoritmos parametrizados, algoritmos online, técnicas de decomposição e balanceamento, algoritmos distribuídos e paralelos.
- Complexidade Computacional: análise de problemas e algoritmos, NP-completude, reduções polinomiais, inaproximabilidade, classes de complexidade de tempo e espaço, complexidade parametrizada, análise amortizada, abordagens lógicas à complexidade computacional, aplicações.
- Computabilidade: modelos teóricos de computação, métodos e linguagens formais, autômatos, computabilidade de Turing e generalizações, teoria da prova, teoria da recursão, reduções, decidibilidade, definibilidade, conjuntos enumeráveis, sistemas de provas interativas, matemática reversa, redes de Petri, aplicações.
- Otimização Combinatória: otimização em redes, programação dinâmica, estruturas combinatórias, combinatória poliédrica, métodos exatos e aproximativos, métodos de busca global e de busca local, heurísticas, modelagem e aplicações.
- Programação Matemática: programação linear inteira e não-linear, programação multiobjetivo, programação por restrições, otimização estocástica, otimização robusta, formulações, decomposições, métodos de solução exatos, heurísticos e híbridos.
- Teoria dos Grafos e Combinatória: problemas clássicos, caracterização estrutural, reconhecimento, classes de grafos, estruturas proibidas, desenho e layout de grafos, teoria espectral, teoria extremal, grafos aleatórios, algoritmos, complexidade, aplicações.
- Teoria da Informação, Números e Criptografia: fundamentos, compressão, teoria de códigos, corretores de erro, codificação de fonte, sistemas numéricos, aritmética modular, congruências, divisibilidade, criptoanálise, protocolos com segurança demonstrável, algoritmos, aplicações.
- Teoria dos Jogos e da Decisão: fundamentos, sistemas em equilíbrio, equilíbrio de Nash, dominância, preço da anarquia e da estabilidade, leilões e mecanismos, precificação, estratégias competitivas, jogos cooperativos, jogos combinatórios, pesquisa operacional, algoritmos, aplicações.
- Geometria Computacional: algoritmos e estruturas de dados para problemas geométricos estáticos e cinéticos, espaços métricos, geometria de distâncias, estruturas baseadas em propriedades geométricas, estruturas espaciais, aplicações.
- Aplicações e Problemas Práticos: alocação de recursos, apoio à tomada de decisão, biologia computacional, compiladores, economia, escalonamento, engenharias, estrutura molecular, pesquisa operacional, probabilidade e estatística, processos produtivos, reconhecimento de padrões, redes de computadores, redes complexas, redes livres de escala e redes web, robótica, roteamento, segurança de código, sistemas e redes, sistemas paralelos e distribuídos, teoria de conjuntos, visualização de dados, aplicações com grandes massas de dados, aplicações dinâmicas, aplicações de tempo real.
Instruções de Submissão
- Os trabalhos devem ser submetidos na forma de resumos estendidos, elaborados preferencialmente em LaTeX, seguindo o formato de artigos da SBC, disponível em https://www.sbc.org.br/wp-content/uploads/2024/07/modelosparapublicaodeartigos.zip. Devem ter no máximo 04 (quatro) páginas, sem incluir as referências, que poderão estar em uma página adicional.
- O artigo poderá ter opcionalmente um apêndice, fora do limite de páginas, contendo material de apoio adicional (como provas, detalhes de implementação ou experimentos computacionais), que não puderam ser incluídos no artigo submetido. O apêndice poderá ser usado para fins de avaliação do trabalho, mas não fará parte do texto publicado nos anais em caso de aceitação do artigo.
- O trabalho submetido será revisado com método single-blind por pelo menos dois revisores, sejam membros do comitê de programa ou pesquisadores por eles indicados.
- Os artigos podem ser escritos em português ou inglês.
- Os autores deverão seguir as recomendações do Código de Conduta para Autores em Publicações da SBC na elaboração de seus trabalhos.
- As submissões devem ser feitas no sistema JEMS através do link: https://jems3.sbc.org.br/etc
Inscrição e Participação no Evento
Devido a limitações de espaço na programação do CSBC, o número de trabalhos selecionados para apresentação oral provavelmente será menor do que em edições anteriores do ETC. Desta forma, a depender do número de trabalhos aceitos, alguns trabalhos serão convidados a serem apresentados no formato de pôster.
A inscrição pagante de ao menos um autor de cada artigo aceito é obrigatória para sua inserção nos Anais do evento. Autores com mais de um artigo aprovado, em qualquer evento do CSBC, podem realizar o pagamento de uma única inscrição, acrescida de uma “taxa de publicação extra” por artigo adicional. Os organizadores se reservam o direito de não incluir nos Anais aqueles trabalhos que não forem apresentados durante o evento.
Publicação dos Trabalhos
Independentemente da forma de apresentação (oral ou pôster), os artigos aceitos serão indexados com DOI e publicados nos anais do evento que serão disponibilizados online na SBC OpenLib (SOL), o portal de conteúdo da SBC.
Datas Importantes
- Prazo para submissão dos trabalhos: 30 de março de 2026 (PRAZO FINAL)
- Divulgação dos resultados:
04 de maio de 202606 de maio de 2026 - Envio das versões finais dos artigos: 18 de maio de 2026
- Prazo de inscrição dos autores: 18 de maio de 2026
- CSBC 2026: 19 a 23 de julho de 2026
Premiações
Os resumos estendidos submetidos ao ETC 2026 estarão automaticamente concorrendo ao prêmio de melhor trabalho do evento, que será escolhido por uma comissão especialmente designada para esse fim, composta por pelo menos três membros. A comissão levará em conta, além do resumo submetido e da apresentação, as avaliações dos revisores.
Palestrantes Convidados
- Márcia Cappelle (UFG): “Coloração como ferramenta de identificação local em grafos”
- Uéverton Souza (IMPA): “Hitting forbidden induced subgraphs on bounded treewidth graphs”
Artigos Aceitos
- Uma Aproximação FPT Linear para o Problema da Cobertura Mínima por Varredura
- Lucas de Oliveira Silva, Lehilton Lelis Chaves Pedrosa
- Set graphs are not definable in MSO1
- Bruno Bandeira Monteiro, Márcia Rosana Cerioli, Petrucio Viana
- Rotulação de arestas semiforte em grafos com grau máximo elevado
- Luis Gustavo da Soledade Gonzaga, C. N. Campos
- p−Role Assignment for Cayley Graph Hℓ,p
- Athos José de Araújo, Paulo Felipe Candia Cazon, André da Cunha Ribeiro
- Placement of charging stations for energy-constrained robots in spider graphs
- Lucas Cardoso Pereira, Santiago Ravelo
- Orthogonality between acyclic subdigraphs and paths in digraphs
- Caroline Ap. P. Silva, Cândida Nunes da Silva, Orlando Lee
- On the conformability of the disjoint union of graphs
- Luerbio Faria, Mauro Nigro, Myriam Preissmann, Diana Sasaki
- On the (2,1)-total number of indifference graphs
- M. M. Omai, Atílio Gomes Luiz, C. N. Campos
- On Rainbow Coloring of Quadrilateral Snake Graphs
- Felipe Bertoluci Wendt, Aleffer Rocha, M. M. Omai
- On r-dynamic coloring of graphs in subclasses of planar and circulant graphs
- Juan Gutierrez, Grover Ugarte
- O Jogo da Cobertura de Vértices em Grafos
- Josefran Bastos, Fabricio Siqueira Benevides, Thiago Marcilon, Nicolas Martins, Nicolas Nisse, Rudini Menezes Sampaio
- NP-Completeness of Independent Locating-Dominating Sets in Planar Bipartite and Subcubic Graphs
- Dayllon Vinícius Xavier Lemos, Márcia R. Cappelle, Erika M. M. Coelho, Leslie Foulds, Humberto Longo
- Mixed Integer Linear Programming Model for the Super-Colored Path Problem in Digraphs
- Rafael Marian, Wesly Carmesini Ataide, Rafael de Santiago, Álvaro Junio Pereira Franco
- Minimum k-labeled triangle forest: complexity and greedy approximations
- Santiago Ravelo, Cristina G. Fernandes
- Lower Bounds on the Convergence to Nash Equilibrium in the Bin Packing Game
- André Vignatti, Flavio K. Miyazawa
- Jogo Normal Partizan de Dominação nas Estrelas
- Edileudo Maciel Filho, Jefter Maciel Paz, Rudini Menezes Sampaio, João Marcos Brito
- Hardness results on parity subdivisions in digraphs
- Philipe Serra, Ana Karolinna Maia de Oliveira, Cibele Matos Freire
- Filling more gaps on the edge coloring problem of split graphs
- Fernanda Vieira Dias Couto, Diego Ferraz, Celina M. H. Figueiredo, Sulamita Klein
- Espectro do número de intervalo na convexidade P3→\overrightarrow{P_3}
- Álvaro Farias, Ana Karolinna Maia, Nalbert da Costa
- Escalonamento de Tarefas com Níveis Variados de Criticidade
- Elisa DellArriva, Flavio K. Miyazawa
- Distance-k Domination in Triangular Matchstick Graphs and Triangulated Rectangular Grids
- Juan Gutierrez, Jorge Neira
- Complexity of the Girth Problem on Arc-colored Digraphs
- Manoel Campelo, Rafael de Paiva Lima Filho, Claudia Linhares Sales
- Coloração Total de Grafos Linha de Grafos Completos
- Giovana Badreddine, Hebert Coelho da Silva, Márcia R. Cappelle
- Coloração de identificação local em grafos split-comparabilidade
- Robson Medrado de Oliveira, Márcia R. Cappelle, Hebert Coelho da Silva, Julliano Rosa Nascimento
- Cobrindo as arestas de cactos com caminhos
- Samuel Santos Morais, Ana Karolinna Maia, Carlos Vinícius Gomes Costa Lima
- Cobertura Exata por Caminhos Arco-Íris com Conflitos em Grafos Tricoloridos
- Gustavo Souza, Santiago Ravelo
- Caracterizando facetas do politopo do Subgrafo Gerador Balanceado Máximo via comutação
- Natália Coelho, Manoel Campelo
- Autenticação Baseada em Tokens e Provas de Conhecimento Zero
- Yasmin Criôlo, Ruy José Guerra Barretto de Queiroz
- Atribuição de papéis sob restrições núcleo–periferia em produto corona de grafos
- Jarlilson Guajajara, Diane Castonguay, Julliano Rosa Nascimento
- Aspectos Algorítmicos de Imersões em Digrafos
- Luis Antonio Lopes Bezerra, Ana Karolinna Maia de Oliveira, Jonas Costa
- Arredondamento Aleatorizado para o Problema de Localização de Instalações Justo
- Jovânio José Galvão Júnior, Lehilton Lelis Chaves Pedrosa
- Análise assintótica e empírica de filas de prioridade avançadas aplicadas ao Algoritmo de Dijkstra
- Ana Carla de Araújo Fernandes, Lucas Castro, Thailsson de Andrade, Rosiane de Freitas
- An Exact Framework for the Trigger Arc Traveling Salesman Problem
- Miguel Alessandro Miní Huambachano, Lucas de Oliveira Silva, Flavio K. Miyazawa
- An Approximation Algorithm for the Rich-Club Coefficient via Sample Complexity
- Eric Fukuyama, Leandro Miranda Zatesko, Murilo V. G. da Silva
- ALNS com Simulated Annealing e Shortest Path Heuristic para o Problema da Árvore de Steiner Clusterizada
- João Guilherme Guimarães e Silva, Alexandre Ribeiro
- Algoritmo para Alinhamento de Sequências em Grafos de Sequências com Economia de Espaço
- Thayná Gimenez, Eloi Araujo, Said Sadique Adi, Lucas Barbosa Rocha
- Ajuste Dinâmico de Tempos Semafóricos usando Previsão de Tráfego e Controle Fuzzy Sequencial
- Erick Lucas, Manoel Henrique de Oliveira Camargo, Maria José Pereira Dantas
- A faster and adaptive partition function for Quicksort
- Victor Almeida Campos, Israel Mendes, Rodrigo Nogueira, Wladimir Araújo Tavares
- A Concentration Inequality for Multiple Estimators Based on a Polynomial-Time Computable Metric
- Vinícius Maurício Ribeiro, André Vignatti
- A Clustering-Based Max-SAT Formulation for the Capacitated Vehicle Routing Problem with Time Windows
- Pedro Ferreira, Denilson Cordeiro, Rafael Dantas, Carlos Araújo, Alexandre Arruda
Coordenação
- Carla Negri Lintzmayer (UFABC) – Coordenadora Geral
- Rudini Menezes Sampaio (UFC) – Coordenador Geral
- Vinícius Fernandes dos Santos (UFMG) – Coordenador Geral
Comitê de Programa
- Ana Flávia Uzeda dos Santos Macambira (UFPB)
- André Vignatti (UFPR)
- Atílio Gomes Luiz (UFC)
- Carla Negri Lintzmayer (UFABC)
- Carlos Hoppen (UFRGS)
- Guilherme de Castro Mendes Gomes (UFMG)
- Jesus Ossian Cunha Silva (DEMA-UFC)
- Julliano Rosa Nascimento (UFG)
- Lehilton Lelis Chaves Pedrosa (UNICAMP)
- Márcia Cappelle (UFG)
- Márcia Helena Costa Fampa (UFRJ)
- Pedro Henrique Del Bianco Hokama (UNIFEI)
- Raquel de Souza Francisco Bravo (UFF)
- Roberto Freitas Parente (UFBA)
- Rosiane de Freitas Rodrigues (UFAM)
- Rudini Menezes Sampaio (DC-UFC)
- Sheila Morais de Almeida (UTFPR)
- Thiago Braga Marcilon (UFCA)
- Uéverton dos Santos Souza (UFF)
- Vinícius Fernandes dos Santos (UFMG)
- Warley Gramacho da Silva (UFT)
Contato
ceaco.sbc@gmail.com
