| Edge Intersection Graphs of Paths on a Triangular Grid Vitor de Luca, María Pía Mazzoleni, Fabiano Oliveira, Jayme Szwarcfiter |
| Relação entre classes de grafos com contagem de intervalo k Lívia Medeiros, Jayme Szwarcfiter, Fabiano Oliveira |
| Emparelhamento Conexo Ponderado é NP-completo Guilherme Gomes, Bruno Masquio, Paulo Pinto, Vinicius dos Santos, Jayme Szwarcfiter |
| Finura em Grafos Cordais Vinicius dos Santos, Bernardo Amorim |
| Heavy and leafy trees Cristina Fernandes, Carla Lintzmayer, Mario César San Felice |
| Instances for the Maximum Clique Problem with Hardness Guarantees Victor Campos, Renato Carmo, Rodrigo Nogueira |
| Coloração Harmoniosa Júlio César Araújo, Marcio Santos, Ana Beatriz Martins |
| Uma Heurística Baseada em Programação Linear Inteira para o Problema do Empacotamento de Soma Mínima Rafael Schouery |
| Bipartizando Grafos Livres de P_6 pela Remoção de um Emparelhamento Carlos Vinícius Lima, Cícero Morais |
| Minimum Density of Identifying Codes of Hexagonal Grids with a Finite Number of Rows Gabriel Sobral, Rudini Sampaio, Yoshiko Wakabayashi |
| Lights Out em grafos: apagando luzes da menor maneira Ighor Brito, Fernanda Couto, Willian Sé |
| A generalization of the block decomposition for k-connected graphs Jared León |
| Three Questions about Equitable Total Coloring of Small Cubic Graphs Matheus Adauto, Celina Figueiredo, Diana Sasaki |
| Um estudo sobre emparelhamentos e a coloração total Sérgio Fusquino, Diana Sasaki, Mauro Nigro, Ingrid Borchet |
| The conformable condition for Nanodiscs Mariana Cruz, Celina Figueiredo, Diana Sasaki, Marcus Vinicius Costa |
| A conformabilidade dos grafos subcúbicos conexos Luerbio Faria, Mauro Nigro, Diana Sasaki |
Dominação e independência são temas bastante estudados na literatura de teoria dos grafos, com interesses teórico e prático. Um conjunto dominante S em um grafo G é um conjunto de vértices tal que todo vértice em V \ S é adjacente a um vértice em S e o número de dominação de G é a mínima cardinalidade de um conjunto dominante de G. Um conjunto I de vértices de um grafo G é independente se quaisquer dois vértices em I não são adjacentes e o número de independência de G é a cardinalidade de um conjunto independente máximo em G. Muitas variações para os problemas de dominação e independência surgiram desde a sua definição, como k-dominação, dominação total, dominação localizada, k-independência, etc…. Nesta palestra veremos algumas destas variações e apresentaremos alguns resultados relacionados a esses problemas.
Possui graduação em Ciência da Computação pela Universidade Católica de Goiás (2005), mestrado em Ciência da Computação pela Universidade Federal de Goiás (2007) e doutorado em Engenharia de Sistemas e Computação pela COPPE/UFRJ (2012). Atualmente é professora da Universidade Federal de Goiás. Tem experiência na área de Ciência da Computação, com ênfase em Teoria dos Grafos e Complexidade de Computação. Membro do Comitê Gestor da Comissão Especial em Algoritmos, Combinatória e Otimização da SBC.
| O Problema do Número Clique Orientado Absoluto é NP-completo Erika Coelho, Hebert Coelho, Luerbio Faria, Mateus Ferreira, Sulamita Klein |
| k-independência em prismas complementares é NP-completo Otávio Mortosa, Márcia Cappelle, Erika Coelho |
| Complexidade do Positional Knapsack Problem Mauro da Silva, Lehilton Pedrosa, Rafael Schouery |
| Problemas de Particionamento de Grafos em Árvores Monocromáticas Diego Costa, Vinicius dos Santos, Phablo Moura |
| (Sub)Fall Coloring and b-Coloring Parameterized by Treewidth Davi de Andrade, Ana Shirley da Silva |
| On the Partial Grundy Number of a Graph Minus a Matching Kenny Domingues,, Ana Shirley da Silva |
| Galáxias como backbone em colorações backbone Júlio César Araújo, Rayane Castro, Alexandre Cezar |
| Proper edge colorings of complete graphs without repeated triangles Lucas Colucci, Fábio Botler, Paulo Matias, Guilherme Mota, Roberto Parente, Matheus Secco |
Recognizing which Cographs are Set Graphs |
| Número (p,1)-total de near-ladders e Petersen generalizados M. M. Omai, C. N. Campos, Atílio Luiz |
| Sobre o numero de cruzamentos do grafo de Kneser K(n, 2) Antônio David Sousa, Luerbio Faria, Jonas Carneiro, Mario Valencia-Pabon |
| On Tuza’s conjecture in even co-chain graphs Luis Chahua, Juan Gutiérrez |
| Análise do Código de Steane por Randomized Benchmarking Anderson Barbosa, Franklin Marquezino, Renato Portugal |
| Dimension Reduction for Projective Clustering Rafael Lima |
| Heurísticas para o Problema de Partição de Strings Comuns Mínima Wallesson Silva, Paulo Henrique, Fábio Dias, Emanuel Coutinho, Críston Souza |
| Leasing K-Center, nova restrição e abordagem heurística Valdomiro Roberto Neto, Alexandre Ribeiro, Welverton Silva, Guilherme Londe |
Os problemas de empacotamento estão entre os problemas de grande interesse e importância por possuirem um grande número de aplicações espalhadas em diversas áreas. Nestes problemas, buscamos colocar, de uma forma econômica, uma coleção de objetos dentro de recipientes. Em muitas aplicações, os objetos podem representar itens palpáveis (como barras, discos, caixas, móveis etc.) para serem colocados dentro de recipientes com uma ou mais dimensões relevantes (como contêineres, caixas, veículos etc.). Em outras, podem estar representados eletronicamente (como imagens de propaganda em painéis eletrônicos e páginas web, trechos de memória para programas de computador, fluxo de dados em transmissões eletrônicas etc.). Estes problemas também podem ser vistos como problemas de corte, onde um material (recipiente) é cortado para a obtenção de objetos menores (como placas de vidro, tecido, couro etc.). Nesta palestra, veremos alguns problemas de empacotamento, comentaremos aspectos da complexidade computacional e apresentaremos algumas abordagens e técnicas de resolução.
Flávio K. Miyazawa, fez a graduação em ciência da computação na Universidade Federal do Mato Grosso do Sul (1990), mestrado (1993) e doutorado (1997) na área de otimização combinatória na Universidade de São Paulo. Desde 1998 é professor do Instituto de Computação da Universidade Estadual de Campinas. Seus interesses de pesquisa estão voltados a problemas de otimização combinatória, algoritmos de aproximação e programação inteira.
| On the maximum number of edges in a graph with prescribed walk-nonrepetitive chromatic number João Pedro de Souza, Wanderson Lomenha, Fábio Botler |
| Seymours Second Neighborhood Conjecture on sparse random graphs Fábio Botler, Phablo Moura, Tássio Naia |
| Formulações para o Problema da k-Floresta Geradora Mínima José Robertty Costa, Gabriel Sousa, Manoel Campelo |
| Algorithms for a Restricted Genome Median Problem Helmuth Silva, Diego Rubert, Eloi Araujo, Fábio Martinez |
| Minimizing Infection in a Topology using Mathematical Programming Wesly Ataide, Alvaro Franco, Rafael de Santiago, Pedro Castellucci |
O Encontro de Teoria da Computação, em sua sétima edição, tem se apresentado como 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 a 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.
Convidamos a comunidade científica, em particular àqueles atuando na área de teoria da computação e áreas correlatas, a submeterem seus resultados de pesquisa, por meio de resumos estendidos, ao VII Encontro de Teoria da Computação, evento satélite do Congresso da Sociedade Brasileira de Computação (CSBC). Trabalhos envolvendo alunos de pós-graduação ou graduação são especialmente bem-vindos. Os trabalhos selecionados deverão ser apresentados oralmente em sessões técnicas do ETC 2022.
Os tópicos de interesse do ETC 2022 incluem, mas não estão limitados a:
Formato dos artigos
Os trabalhos devem ser submetidos na forma de resumos estendidos, elaborados preferencialmente em LaTeX, seguindo o formato de artigos da SBC, 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 fará parte do texto publicado nos anais em caso de aceitação do artigo.
Meio de submissão
A submissão dos artigos será eletrônica, em formato PDF, e será feita por meio do sistema JEMS a partir do link https://jems.sbc.org.br/etc2022, começando em 15/12/2021.
Processo de revisão
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.
Para que um artigo aceito seja apresentado e incluído nos anais do evento, é necessário que ao menos um dos autores do artigo realize a sua inscrição no evento na categoria profissional. Cada inscrição na categoria profissional dá direito à publicação de um único artigo, considerando qualquer um dos eventos-base ou eventos-satélite do CSBC. Autores com mais de um artigo aprovado em qualquer evento do CSBC deverão pagar uma “taxa de publicação” por artigo adicional. O valor dessa taxa pode ser visto na página de inscrições do CSBC 2022.
Os artigos aceitos serão publicados na SBC Open Lib, a biblioteca digital da SBC, na série Anais do Encontro de Teoria da Computação (ETC) (ISSN 2595-6116) disponível em https://sol.sbc.org.br/index.php/etc. Todos os artigos serão indexados com DOI.
Os resumos estendidos submetidos ao ETC 2022 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 as avaliações dos revisores, além de sua própria análise dos trabalhos.
Organizadores gerais:
Manoel Bezerra Campêlo Neto (UFC)
Cristina Gomes Fernandes (USP)
Vinicius Fernandes dos Santos (UFMG)
Organizadores do comitê de programa:
Manoel Bezerra Campêlo Neto (UFC)
Cristina Gomes Fernandes (USP)
Vinicius Fernandes dos Santos (UFMG)
Apoio local:
Luis Felipe Cunha (IC/UFF)
Comitê de programa:
Manoel Campêlo (UFC) – mcampelo@ufc.br
