PROGRAMAÇÃO
ENCONTRO DE TEORIA DA COMPUTAÇÃO
PROGRAMAÇÃO
| PROGRAMAÇÃO DIA 1 – 15/07, Segunda-feira | ||
| Sala: Muruci / MU-3 | ||
| 09:00 – 09:20 | Abertura | |
| 09:20 – 10:00 | Palestra 1: Algoritmos eficientes para um problema de busca em grafos dirigidos acíclicos
Prof. Carlos E. Ferreira (USP, Brasil) |
|
| 10:00 – 12:00 | Sessão Técnica I | |
| 01 | Coloração equilibrada de grafos n-StarClique | Matheus Guedes (UFMG – Brasil),
Vinicius dos Santos (UFMG – Brasil) |
| 02 | Algoritmos eficientes para emparelhamentos
desconexos em grafos cordais e grafos bloco |
Bruno Masquio (UERJ – Brasil),
Paulo Pinto (UERJ – Brasil), Jayme Szwarcfiter (UFRJ – Brasil) |
| 03 | Reconhecimento de Grafos Fino de
Precedência |
Flavia Bonomo (UBA – Argentina),
Fabiano Oliveira (UERJ – Brasil), Moysés Sampaio Júnior (UFRJ – Brasil), Jayme Szwarcfiter (UFRJ – Brasil) |
| 04 | Equitable Partition of Graphs into
Independent Sets and Cliques |
Bruno Monteiro (UFMG – Brasil),
Vinicius dos Santos (UFMG – Brasil) |
| 12:00 – 14:00 | Almoço | |
| 14:00 – 16:00 | SECOMU | |
| 16:00 – 16:30 | Coffee-break | |
| 16:30 – 17:10 | Palestra 2: Computations, Paths, Types and Proofs
Prof. Ruy de Queiroz (UFPE, Brasil) |
|
| 17:10 – 19:10 | Sessão Técnica II | |
| 05 | Aspectos de complexidade parametrizada e problemas análogos em problemas de lista coloração de grafos e suas variações | Simone Gama (UFAM – Brasil),
Rosiane de Freitas (UFAM – Brasil), Uéverton Souza (UFF – Brasil) |
| 06 | Convexidade em Grafos Linha de Bipartidos | Vitor Ponciano (UFRJ – Brasil),
Rômulo Oliveira (UFRJ – Brasil) |
| 07 | Some exact values for the diameter in Cayley graph Hl,p | Caroline Patrão (UFRJ – Brasil),
Luis Kowada (UFF – Brasil), Diane Castonguay (UFG – Brasil), André Ribeiro (Instituto Federal Goiano Rio Verde – Brasil), Celina de Figueiredo (UFRJ – Brasil) |
| 08 | A proof for Berge’s Dual Conjecture for
Bipartite Digraphs |
Caroline Silva (UFSCar-Sorocaba – Brasil),
Cândida da Silva (UFSCar-Sorocaba – Brasil), Orlando Lee (UNICAMP – Brasil) |
| PROGRAMAÇÃO DIA 2 – 16/07 – Terça-feira | ||
| Sala: Muruci / MU-3 | ||
| 09:00 – 09:40 |
Palestra 3: O papel dos grafos na área de passeios quânticos Prof. Renato Portugal (LNCC, Brasil) |
|
| 10:00 – 12:00 | Sessão Técnica III | |
| 09 | Two simplified versions of Red-Blue Facility Location |
Cristina Fernandes (USP – Brasil), Rafael Pocai (USP – Brasil) |
| 10 | Formulações e heurísticas para os problemas leasing k-median e leasing k-center |
Jorge dos Santos (PUC-GO – Brasil), Guilherme Londe (PUC-GO – Brasil), Alexandre Ribeiro (PUC-GO – Brasil), Welverton da Silva (UNICAMP – Brasil) |
| 11 |
A Constant-Factor Approximation for the Generalized Cable-Trench Problem |
Marcelo Benedito (UNICAMP – Brasil), Lehilton Pedrosa ((UNICAMP – Brasil), Hugo Rosado (UNICAMP – Brasil) |
| 12 |
Um esquema de aproximação para um problema de empacotamento com cenários |
Yulle Borges ((UNICAMP – Brasil), Thiago de Queiroz (UFG – Catalão – Brasil), Vinícius Lima ((UNICAMP – Brasil), Flávio Miyazawa ((UNICAMP – Brasil), Lehilton Pedrosa ((UNICAMP – Brasil) |
| 12:00 – 14:00 | Almoço | |
| 14:00 – 16:00 | SECOMU | |
| 16:00 – 16:30 | Coffee-break | |
| 16:30 – 17:10 |
Palestra 4: Parameterized complexity: basic concepts and some results on a graph coloring problem Prof. Vinicius F. dos Santos (UFMG, Brasil) |
|
| 17:10 – 18:10 | Sessão Técnica IV | |
| 05 | Transtemporal edges and crosslayer edges in incompressible high-order networks |
Felipe Abrahão (LNCC – Brasil) Klaus Wehmuth (LNCC – Brasil) Artur Ziviani (LNCC – Brasil) |
| 06 | Revising a Model of Crime and Punishment | Ariel Arbiser (UBA – Argentina) |
| 07 |
Number-On-Forehead Communication Complexity of Data Clustering with Sunflowers |
Fabricio Mendoza (Universidad Nacional de Asunción – Paraguay) Marcos Villagra (Universidad Nacional de Asunción – Paraguay) |
Dia 15/07 das 09:20 às 10:00 – Palestra 1:
Busca em Grafos e Relações de Parentesco
Palestrante: Carlos E. Ferreira (IME-USP)
Resumo: Apresentaremos nesta palestra um problema que ocorre na área de estudo do parentesco da área de Antropologia, e suas relações com encontrar junções em grafos dirigidos acíclicos (DAG). Dizemos que um vértice s é uma junção dos vértices u e v de um DAG se existem caminho internamente disjuntos de s a u e de s a v. Mostramos um algoritmo eficiente baseado em busca em profundidade para encontrar os pares de vértices que admitem um vértice s como junção. O algoritmo
induz uma relação minimax que pode ser mostrada para um tipo especial de grafos, os grafos fluxo (flowgraphs).
Este trabalho foi feito em co-autoria com Álvaro Junio Pereira Franco (UFSC) e Marcio Ferreira da SIlva (FFLCH-USP).
Dia 15/07 das 16:30 às 17:10 – Palestra 2:
Computations, Paths, Types and Proofs
Palestrante: Ruy de Queiroz (UFPE)
Abstract: What is a proof of an equality statement? In what sense can it be seen as a homotopy? Motivated by looking at equalities in type theory as arising from the existence of computational paths (i.e., rewrites) between two formal objects, it seems useful to review the role and the power of the notion of propositional equality as formalised in the so-called Curry-Howard functional interpretation. In a recent series of applications of such a connection between type theory and homotopy theory, we use a formalisation of computational path to obtain some results of algebraic topology and, with support of the Seifet-Van Kampen Theorem, we show how to calculate the fundamental group of the circle, the Klein bottle, the torus, and the two-holed torus. As a matter of fact, this shows that a single concept may serve as a bridging bond between several areas of mathematics: path. Computation: convertibility between λterms. (Algebraic) Topology: homotopy theory. Logic: proofs of equality. (Higher) Categories: polycategories; (Higher) Algebra: ∞-groupoids.
Dia 16/07 das 09:00 às 09:40 – Palestra 3:
O papel dos grafos na área de passeios quânticos
Palestrante: Renato Portugal (LNCC)
Resumo: A área de passeios quânticos tem destaque na computação quântica, pois muitos algoritmos quânticos importantes foram obtidos usando passeios quânticos como, por exemplo, o algoritmo para determinar se uma lista de dados tem elementos repetidos. Historicamente, a área de passeios quânticos teve início na década de 90, porém só recentemente ficou claro que, para esta área avançar, é necessária uma investigação mais profunda do papel dos grafos tanto para definir corretamente os diversos modelos de passeios quânticos quanto para provar novos teoremas e obter de novos resultados.
Dia 16/07 das 16:30 às 17:10 – Palestra 4:
Parameterized complexity: basic concepts and some results on a graph coloring problem
Palestrante: Vinicius F. dos Santos (UFMG)
Abstract: In this this talk we review some of the main concepts of parameterized complexity and show some new results on a coloring problem known as Weighted Coloring. We illustrate some of the main concepts by presenting a kernel for the problem and also by ruling out the existence of polynomial sized kernels unless a wellaccepted complexity hypothesis fails. We also mention briefly other results on the problem.