ETC

Menu ocultar
ETC 2021 – VI Encontro de Teoria da Computação
Programação
Chamada de Trabalhos
Organização
Inscrições

ETC 2021 – VI Encontro de Teoria da Computação

Evento Satélite do CSBC 2021

18 a 23 de Julho de 2021

Programação

Abertura

19

Julho

09:00

Sessão Técnica 1

19

Julho

09:20

  • The (2, 1)-total number of near-ladder graphs

    M. M. Omai (University of Campinas),
    C. N. Campos (UNICAMP),
    Atílio Luiz (Universidade Federal do Ceará)

  • Sobre Rotulações L(h, k) de Caterpillars

    João Paulo Castilho (Universidade Estadual de Campinas),
    C. N. Campos (UNICAMP),
    Leandro Zatesko (Federal University of Technology – Paraná (UTFPR), Campus Curitiba)

  • Sobre $(2,1)$-colorações em grafos exoplanares maximais

    A. L. Jonck Junior (Universidade Estadual de Campinas),
    C. N. Campos (UNICAMP)

  • On $L(h,k)$-labelings of oriented graphs

    Lucas Colucci (Universidade de São Paulo)

  • On the Complexity of Subfall Coloring of Graphs

    Davi de Andrade (Universidade Federal do Ceará),
    Ana da Silva (Universidade Federal do Ceará)

  • Lower Bounds for the Partial Grundy Number of the Lexicographic Product of Graphs

    Kenny Domingues (Universidade Federal do Ceará (UFC)),
    Yuri Oliveira (Universidade Federal do Ceará (UFC)),
    Ana da Silva (Universidade Federal do Ceará)

  • Limites superiores para a rotulação L(3,2,1) de famílias de grafos subcúbicos

    Davi Florencio (Universidade Federal do Ceará),
    Atílio Luiz (Universidade Federal do Ceará)

  • Caminhos supercoloridos em digrafos

    Alvaro Franco (Federal University of Santa Catarina),
    Marcelo Vendramin (Universidade Federal de Santa Catarina)

Palestra: On edge domination of graphs Jayme Luiz Szwarcfiter (UFRJ e UERJ)

19

Julho

16:30

Let G be a graph. Say that an edge of G dominates itself and every other edge adjacent to it. An edge dominator of G is a subset of edges dominating all the edges of G. The problem of edge domination is to find a minimum cardinality edge dominator E’. Say that E’ is an efficient dominator when each edge of G is dominated exactly once. However, if only the edges of G – E’ are dominated exactly once, then E’ is called a perfect dominator. In this talk, we describe results on these three types of edge dominations. The case of weighted domination is also considered.

Sobre Jayme Luiz Szwarcfiter (UFRJ e UERJ)

CV: Possui graduação em Engenharia Eletrônica pela UFRJ, 1967, mestrado em Engenharia de Sistemas e Computação pela UFRJ, 1971, e doutorado em Ciência da Computação, pela University of Newcastle Upon Tyne, Inglaterra, 1975. Realizou pós-doutorados na University of California, Berkeley, EUA, 1979-80, na University of Cambridge, Inglaterra, 1984-85 e na Université Paris XI, França, !992-94. Iniciou a sua carreira acadêmica na UFRJ, onde alcançou as posições de Professor Emérito do Instituto de Matemática, Professor Titular do Programa de Engenharia de Sistemas da COPPE, e Pesquisador do Núcleo de Computação Eletrônica. Foi pesquisador visitante em diversas instituições do país e do exterior. Atualmente é Pesquisador Visitante do Instituto de Matemática e Estatística da UERJ. Recebeu diversos prêmios e distinções, entre os quais o Prêmio Álvaro Alberto do Ciência e Tecnologia, MCTI-CNPq; o Prêmio Giulio Massarani de Mérito Acadêmico da COPPE; o Prêmio de Mérito Científico da Sociedade Brasileira de Computação; o Prêmio Louis Leloir do Ministerio de Ciencia, Tecnologia y Inovación Productiva, da Argentina; os graus de Comendador e Grã-Cruz da Ordem Nacional do Mérito Científico, MCTI; o Prêmio Elon Lages Lima, da Sociedade Brasileira de Matemática e Sociedade Brasileira de Matemática Computacional. Foi eleito membro titular da Academia Brasileira de Ciências. Atua nas áreas de Algoritmos, Teoria da Computação e Matemática Discreta. Orientou dezenas de mestres e doutores, que atualmente são docentes de várias universidades do país e do exterior. Foi membro de comitês de julgamento de diversos órgãos de fomento. Em especial, foi Membro do Comitê Assessor de Ciência da Computação do CNPq, nos períodos: 1978-79, 1981-83, 1994-96, 2000-02 e 2007-10.

Lattes: http://lattes.cnpq.br/2002515486942024

Sessão Técnica 2

19

Julho

17:20

  • Linial’s Conjecture for Matching-Spine Digraphs

    Jadder Cruz (IC-Unicamp),
    Cândida Silva (University of São Carlos at Sorocaba),
    Orlando Lee (Universidade Estadual de Campinas)

  • Sobre o Número de Orientação Própria de Grafos Cordais

    Alexandre Cezar (Universidade Federal do Ceará),
    Júlio César Araújo (Universidade Federal do Ceará),
    Vinicius dos Santos (Universidade Federal de Minas Gerais),
    Ana da Silva (Universidade Federal do Ceará),
    Carlos Vinícius Gomes Costa Lima (Universidade Federal do Cariri)

  • Árvores Ramsey-restritas mínimas

    Mauricio Collares (Universidade Federal de Minas Gerais),
    Antônio Fernandes (Universidade Federal de Minas Gerais),
    Guilherme Oliveira Mota (Universidade de São Paulo),
    Hugo Vicente (Universidade Federal de Minas Gerais)

  • Limite superior algorítmico para a contagem de intervalo

    Lívia Medeiros (Universidade do Estado do Rio de Janeiro (UERJ)),
    Fabiano Oliveira (Universidade do Estado do Rio de Janeiro),
    Jayme Szwarcfiter (Universidade Federal do Rio de Janiero (UFRJ))

  • Emparelhamento Desconexo é NP-Completo

    Guilherme de Castro Mendes Gomes (Universidade Federal de Minas Gerais),
    Bruno Masquio (Universidade do Estado do Rio de Janeiro),
    Paulo Pinto (Universidade do Estado do Rio de Janeiro),
    Vinicius dos Santos (Universidade Federal de Minas Gerais),
    Jayme Szwarcfiter (Universidade Federal do Rio de Janeiro)

Sessão Técnica 3

20

Julho

09:00

  • Stochastic multi-depot capacitated vehicle routing problem with pickup and delivery: heuristic approaches

    Brenner Ojeda Rios (Universidade estadual de Campinas),
    Flavio Miyazawa (University of Campinas),
    Eduardo Xavier (University of Campinas (UNICAMP)),
    Pedro Amorim (Universidade do Porto – Portugal)

  • Heuristics for the Colorful Bin Packing Problem

    Renan Franco da Silva (University of Campinas),
    Yulle Borges (University of Campinas),
    Rafael Schouery (University of Campinas)

  • Spanning Cover Inequalities for the Capacitated Vehicle Routing Problem

    Mario César San Felice (Federal University of São Carlos),
    Pedro Hokama (Federal University of Itajubá),
    Guilherme Arcencio (Universidade Federal de São Carlos),
    Matheus Mattioli (Universidade Federal de São Carlos)

  • Novo teste de redução para o problema da árvore de Steiner com coleta de prêmios

    Gabriel de Azevedo (Universidade de São Paulo),
    Carlos Eduardo Ferreira (USP)

  • Post-Synthesis Optimization of Reversible Circuits

    Edinelço Dalcumune (Universidade Federal dos Vales do Jequitinhonha e Mucuri),
    Luis Kowada (Universidade Federal Fluminense),
    Celina Figueiredo (UFRJ),
    Franklin Marquezino (UFRJ)

  • Um Algoritmo Quântico para um Problema de Distância Estatística

    Henrique Hepp (UFPR),
    Murilo da Silva (Federal University of Parana (UFPR)),
    Leandro Zatesko (Federal University of Technology – Paraná (UTFPR), Campus Curitiba)

  • Rumo a uma Teoria de Domínios da Homotopia

    Daniel Martinez (Universidade Federal de Pernambuco),
    Ruy José Guerra Barretto de Queiroz (Universidade Federal de Pernambuco)

  • Computational Paths and the Fundamental Groupoid of a Type

    Arthur Ramos (Microsoft Redmond – USA),
    Ruy José Guerra Barretto de Queiroz (Universidade Federal de Pernambuco),
    Anjolina Oliveira (UFPE)

  • Calculation of Fundamental Groups via Computational Paths

    Tiago M. L. de Veras (Universidade Federal Rural de Pernambuco),
    Arthur Ramos (Microsoft Redmond – USA),
    Ruy José Guerra Barretto de Queiroz (Universidade Federal de Pernambuco),
    Anjolina Oliveira (UFPE)

Palestra: Extended formulation and valid inequalities for the multi-item inventory lot-sizing problem with supplier selection Rafael Augusto de Melo (UFBA)

20

Julho

16:30

We consider the multi-item inventory lot-sizing problem with supplier selection. The problem consists of determining an optimal purchasing plan in order to satisfy dynamic deterministic demands for multiple items over a finite planning horizon, taking into account the fact that multiple suppliers are available to purchase from. As the complexity of the problem was an open question, we show that it is NP-hard. We propose a facility location extended formulation for the problem which can be preprocessed based on the cost structure and describe new valid inequalities in the original space of variables. Furthermore, we study the projection of the extended formulation into the original space and show the connection between the inequalities generated by this projection and the newly proposed inequalities.

Sobre Rafael Augusto de Melo (UFBA)

Rafael Melo é Professor Adjunto do Instituto de Computação da Universidade Federal da Bahia e especialista em Pesquisa Operacional, com ênfase em Otimização e Inteligência Computacional. É bolsista de Produtividade em Pesquisa Nível 2 do CNPq e Membro Júnior da Academia de Ciências da Bahia. É bacharel e mestre em Ciência da Computação pela Universidade Federal de Lavras e pela Universidade Federal Fluminense, respectivamente. É doutor em Ciências da Engenharia pela Université Catholique de Louvain (Bélgica), tendo desenvolvido sua tese no Center for Operations Research and Econometrics (CORE).

Lattes: http://lattes.cnpq.br/4117373032501782

Sessão Técnica 4

20

Julho

17:20

  • Leafy spanning k-forests

    Cristina Fernandes (University of São Paulo),
    Carla Lintzmayer (Federal University of ABC),
    Mario César San Felice (Federal University of São Carlos)

  • Uma aproximação para o Problema de Reabastecimento em Conjunto com Capacidades

    Miguel Ángel Marfurt Alarcón (State University of Campinas),
    Lehilton Lelis Chaves Pedrosa (Universidade de Campinas)

  • Conjunto de arcos de realimentação sob restrições de forçamento é FPT

    Leonardo Abreu (Universidade Federal do Ceará),
    Manoel Bezerra Campelo Neto (Universidade Federal do Ceará),
    Karolinna Maia (UFC)

  • Problema APSP via Dimensão-VC e Médias de Rademacher

    Alane Lima (Federal University of Paraná (UFPR)),
    André Vignatti (Federal University of Paraná (UFPR)),
    Murilo da Silva (Federal University of Parana (UFPR))

  • New Bounds on Roller Coaster Permutations

    Bruno Netto (Universidade do Rio de Janeiro),
    Fábio Botler (Federal University of Rio de Janeiro)

Chamada de Trabalhos

O VI Encontro de Teoria da Computação (ETC 2021) é 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), 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.

Este evento é voltado para os 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 seja 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.

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.

O evento é aberto para a comunidade, com especial interesse nos alunos em formação de graduação e de pós-graduação.

Tópicos de Interesse

Os tópicos de interesse do ETC 2021 incluem, mas não estão limitados a:

  • Algoritmos: análise e projeto de algoritmos, técnicas de decomposição e balanceamento, algoritmos exatos, algoritmos de aproximação, algoritmos probabilísticos, algoritmos online, algoritmos parametrizados, algoritmos distribuídos e paralelos.
  • Complexidade Computacional: análise de problemas e algoritmos, NP-completude, reduções polinomiais, prova de polinomialidade, classes de complexidade de tempo e espaço, complexidade parametrizada, análise amortizada, inaproximabilidade, 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, definabilidade, conjuntos enumeráveis, sistemas de provas interativas, matemática reversa, redes de Petri, aplicações.
  • Otimização Combinatória: estruturas combinatórias, combinatória poliédrica, métodos exatos e aproximados, métodos de busca global e de busca local, otimização multiobjetivo, otimização estocástica, otimização robusta, otimização em redes, pesquisa operacional, modelagem e aplicações.
  • Programação Matemática: formulações, programação linear inteira e não-linear, programação por restrições, métodos enumerativos, planos de corte, branch-and-bound, branch-and-cut, branch-and-price, branch-cut-and-price, branch-and-prune, métodos híbridos exato-heurístico, programação dinâmica, etc.
  • Teoria dos Grafos e Combinatória: caracterização estrutural, classes de grafos, reconhecimento, estruturas proibidas, problemas clássicos, desenho e layout de grafos, teoria espectral, grafos aleatórios, complexidade, algoritmos, aplicações.
  • Teoria da Informação, Números e Criptografia: fundamentos, teoria de códigos, sistemas numéricos, aritmética modular, congruências, divisibilidade, codificação de fonte, corretores de erro, compressão, criptoanálise, protocolos com segurança demonstrável, algoritmos, aplicações.
  • Teoria dos Jogos e da Decisão: fundamentos, estratégias competitivas, sistemas em equilíbrio, equilíbrio de Nash, dominância, preço da anarquia e da estabilidade, leilões e mecanismos, precificação, jogos cooperativos, jogos combinatórios, pesquisa operacional, algoritmos, aplicações.
  • Geometria Computacional: espaços métricos, geometria de distâncias, algoritmos geométricos, estruturas baseadas em propriedades geométricas, estruturas espaciais, aplicações.

Aplicações em outras áreas de conhecimento 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.

Formato dos Artigos

Os trabalhos devem ser submetidos na forma de resumos estendidos, formatados seguindo o estilo dos artigos da SBC (feito preferencialmente em LaTeX), disponível em http://tinyurl.com/sbc-template-artigos. Devem ter no máximo 04 (quatro) páginas incluindo referências, figuras e tabelas.

O artigo poderá ter opcionalmente um apêndice, fora do limite de 4 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 será publicado, mesmo em caso de aceitação do artigo.

A submissão dos artigos será eletrônica, em formato PDF, por meio do sistema JEMS: https://jems.sbc.org.br/home.cgi?c=3737

Datas Importantes

  • Data limite para submissão dos trabalhos: 12/03 26/03 16/04/2021 (hard)
  • Notificação dos trabalhos aceitos: 30/04 21/05/2021
  • Data limite para envio das versões finais: 14/05 04/06/2021
  • Data limite para envio do comprovante de inscrição: 14/05 04/06/2021

Apresentação dos Trabalhos

Os trabalhos serão selecionados para apresentação oral de cerca de 15 a 20 minutos, a depender do volume de submissões. O melhor trabalho apresentado será objeto de premiação.

Os artigos aceitos serão publicados nos anais do evento, que serão disponibilizados online na SBC OpenLib, o portal de conteúdo da SBC, na série Anais do Encontro de Teoria da Computação. Todos os artigos serão indexados com DOI.

Os organizadores se reservam o direito de não incluir nos anais aqueles trabalhos que, durante o evento, não forem apresentados por um de seus autores ou por algum representante indicado. O formato online está sendo considerado o formato mais provável. Mais informações serão fornecidas no futuro.

Inscrição no Evento

A inscrição pagante de ao menos um autor do artigo é obrigatória para inserção do artigo nos Anais de cada evento. Autores com mais de um artigo aprovado, em qualquer evento, podem realizar o pagamento de uma única inscrição, acrescida de uma “taxa de publicação extra” por artigo adicional.

Organização

Coordenação do ETC 2021

Cláudia Linhares Sales (UFC)
Flávio Keidi Miyazawa (UNICAMP)
Manoel Bezerra Campelo Neto (UFC)
Vinicius Fernandes dos Santos (UFMG)

Steering Committee do ETC

Cláudia Linhares Sales (UFC)
Jayme Luiz Szwarcfiter (UFRJ)
Rosiane de Freitas (UFAM)

Coordenação Local do ETC

Alessandro Mueller (UNIVALI)

Comitê de Programa do ETC

Ana Shirley Ferreira da Silva (UFC)
Andre Luís Vignatti (UFPR)
Candida Nunes da Silva (UFSCAR)
Carla Negri Lintzmayer (UFABC)
Carlos Hoppen (UFRGS)
Celina Miraglia Herrera de Figueiredo (UFRJ)
Claudia Linhares Sales (UFC)
Edna Ayako Hoshino (UFMS)
Fábio Protti (UFF)
Flávio Keidi Miyazawa (UNICAMP)
Franklin de Lima Marquezino (UFRJ)
Gabriel de Morais Coutinho (UFMG)
Guilherme Oliveira Mota (USP)
Hugo Nobrega (UFRJ)
Lehilton Lelis Chaves Pedrosa (UNICAMP)
Manoel Bezerra Campelo Neto (UFC)
Marcel Kenji de Carli Silva (USP)
Marcia Cappelle (UFG)
Mário Sérgio Ferreira Alvim Júnior (UFMG)
Orlando Lee (UNICAMP)
Rafael Santos Coelho (UNIPAMPA)
Roberto Freitas Parente (UFBA)
Rosiane de Freitas Rodrigues (UFAM)
Sheila Morais de Almeida (UTFPR)
Uéverton dos Santos Souza (UFF)
Vinicius Fernandes dos Santos (UFMG)