Seminários 2016-2020

Início › Seminários 2016-2020

Seminários 2016-2020

2020

Data/horário: 06/03/2020 – 10h
Local: Sala de Seminários – Bloco 952
Palestrante: Efraim Rodrigues (MDCC/UFC)
Título: “Estudo de Heurísticas para coloração k-imprópria”
Resumo:“Uma coloração dos vértices de um grafo G = (V,E) é própria se vértices adjacentes recebem cores diferentes. Estudamos neste trabalho uma relaxação desse problema, chamada de coloração k-imprópria, onde, dado um inteiro positivo k, a cor de um vértice qualquer pode ser compartilhada com até k de seus vizinhos. Uma vez que a coloração própria é uma coloração 0-imprópria, a coloração k-imprópria é igualmente um problema difícil, podendo-se, analogamente, abordar o problema através do uso de heurísticas. Neste trabalho, estudamos três heurísticas para o problema de coloração k-imprópria de grafos. Como se faz habitualmente, o estudo aqui almejava estimar o pior desempenho dessas heurísticas. As heurísticas escolhidas foram as heurísticas gulosa, a e b, que só haviam sido definidas até então para colorações próprias. No caso das heurísticas a e b, as suas versões k-impróprias foram definidas e, no caso da heurística b, provamos que a sua aplicação pode não convergir. No caso da heurística gulosa, além de introduzir o conceito de Número de Grundy k-impróprio, generalizamos o conceito de t-átomo, estudamos o parâmetro em árvores binomiais e cografos e apresentamos formulações de programação por restrições e programação inteira, não apenas para a coloração gulosa imprópria, mas também para o Número de Grundy clássico, preenchendo um vácuo naquele estudo.”

Data/horário: 20/02/2020 – 10h
Local: Auditório da PGMAT
Palestrante: Pedro Arraes (PGMAT/UFC)
Título: “Números de envoltória e geodético em classes de grafos orientados.”
Resumo:“Dado um grafo orientado $ D = (V,A) $, um $ (u,v) $-geodético é um $ (u,v) $-caminho (caminho do vértice $ u $ até o $ v $) de menor comprimento. Um conjunto de vértices $ S \subseteq V(D) $ é dito convexo quando esse contém todos os vértices de qualquer $ (u,v) $-geodésico, com $ u,v \in S $. A envoltória de um conjunto $ S \subseteq V(D) $, denotada por $ [S] $, é o menor conjunto convexo contendo $ S $; essa também pode ser definida como a interseção de todos os conjuntos convexos que contêm $ S $. Quando $ [S] = V(D) $ dizemos que $ S $ é um conjunto de envoltória de $ D $, e o número de envoltória de $ D $ é a cardinalidade de um conjunto de envoltória mínimo. Caso cada vértice de $ D $ pertença a algum $ (u,v) $-geodésico com $ u,v \in S $, dizemos que $ S $ é um conjunto geodético de $ D $. Similarmente, o número geodético de $ D $ é a cardinalidade de um conjunto geodético mínimo.Nesta dissertação, além de revisarmos a literatura associada, apresentamos algumas contribuições para esses parâmetros em algumas classes de grafos orientados. A primeira é um limitante superior apertado para torneios, o qual estenderemos para grafos split orientados. Em seguida mostramos que os problemas relacionados a esses parâmetros são NP-completos para grafos bipartidos orientados. No caso do de envoltória, isso também vale para uma subclasse de bipartidos: os cubos parciais. Para o do geodético, o grafo orientado utilizado na redução não só é bipartido, como também é um grafo direcionado acíclico. Por fim, provaremos que é possível obter esses dois parâmetros em tempo polinomial para cactos orientados, uma superclasse de árvores orientadas.”

Data/horário: 18/02/2020 – 14h
Local: Auditório do bloco 910
Palestrante: Ignasi Sau (CNRS, LIRMM, França)
Título: “Introdução sobre complexidade parametrizada”
Resumo:“Nesta palestra faremos uma breve introdução sobre algoritmos e complexidade parametrizada, uma das áreas mais promissoras da teoria da computação. Em seguida será apresentado um dos parâmetros mais importantes em complexidade parametrizada: o treewidth (ou “largura em árvore”). Dependendo do tempo, alguns problemas de nosso interesse particular, em relação com o treewidth, serão introduzidos.”

2019

Data/horário: 29/11/2019 – 13h
Local: Sala de seminários do 952
Palestrante: Andréa Marino (Universidade de Florença)
Título: “On enumeration algorithms”
Slides
Resumo:” In this talk, we revise basic definitions and techniques for listing algorithms, i.e. algorithms aimed to enumerate all the solutions of a problem. In such a context, there are several possible definitions of efficiency for algorithms and the literature provides several techniques to design such algorithms.Some of these techniques are designed to generate subgraphs of a graph satisfying a given property (e.g., being a clique, a cut, a cycle, etc.). Very often we are interested in listing just the maximal subgraphs, i.e. good subgraphs not contained in other good subgraphs.For a certain class of problems (that will be formally defined during the presentation), it has been shown that listing all the maximal solutions in poly time and poly space in a general graph can be done if and only if the same listing problem can be solved in poly time and poly space on a very specific graph. In this talk, we show our recent result that extends this to a wider set of harder problems.”

Data/horário: 22/11/2019 – 13h
Local: Sala de reuniões do bloco 910
Palestrante: Carlos Brito (MDCC/UFC)
Título: “Turing got it right (twice)”
Resumo:“Todo mundo conhece a máquina de Turing: um conjunto finito de estados, um conjunto finito de regras, uma cabeça de leitura/escrita, e uma fita que contém símbolos que são manipulados pela máquina. Apesar da sua aparência modesta, a máquina de Turing é capaz de realizar qualquer computação que você possa imaginar. Mas, é claro, ninguém pensaria em implementar um projeto de computação real na máquina de Turing. O que é curioso, no entanto, é que mesmo em contextos teóricos, já não há muita gente que considere a máquina de Turing como um mecanismo adequado para se investigar o fenômeno da computação: após uma breve apresentação, por razões históricas, os livros passam a desenvolver a teoria utilizando em algum formalismo baseado em programas. Nesse seminário, nós pretendemos recuperar algumas ideias fundamentais de Turing, e argumentar que, apesar da sua popularidade atual, o paradigma de computação como processamento de informações perde de vista o lugar da computação no grande esquema das coisas (cognição, inteligência, linguagem, IA, etc).”

Data/horário: 08/11/2019 – 13h
Local: Sala de Seminários do 952
Palestrante: Júlio Araújo (PGMAT/UFC)
Título: “Weighted proper orientations of trees and graphs of bounded treewidth”
Resumo:“Given a simple graph $G$, a weight function $w:E(G)\rightarrow \mathbb{N} \setminus \{0\}$, and an orientation $D$ of $G$, we define $\mu^-(D) = \max_{v \in V(G)} w_D^-(v)$, where $w^-_D(v) = \sum_{u\in N_D^{-}(v)}w(uv)$. We say that $D$ is a \emph{weighted proper orientation} of $G$ if $w^-_D(u) \neq w^-_D(v)$ whenever $u$ and $v$ are adjacent. We introduce the parameter {\em weighted proper orientation number} of $G$, denoted by $\overrightarrow{\chi}(G,w)$, which is the minimum, over all weighted proper orientations $D$ of $G$, of $\mu^-(D)$. When all the weights are equal to 1, this parameter is equal to the {\em proper orientation number} of $G$, which has been object of recent studies and whose determination is \np-hard in general, but polynomial-time solvable on trees. Here, we prove that the equivalent decision problem of the weighted proper orientation number (i.e., $\overrightarrow{\chi}(G,w) \leq k?$) is (weakly) \np-complete on trees but can be solved by a pseudo-polynomial time algorithm whose running time depends on $k$. Furthermore, we present a dynamic programming algorithm to determine whether a general graph $G$ on $n$ vertices and treewidth at most $tw$ satisfies $\overrightarrow{\chi}(G,w) \leq k$, running in time $\mathcal{O}(2^{tw^2}\cdot k^{3tw}\cdot tw \cdot n)$, and we complement this result by showing that the problem is $W[1]$-hard on general graphs parameterized by the treewidth of $G$, even if the weights are polynomial in $n$.This is a joint work with C. Linhares Sales, I. Sau and A. Silva.”

Data/horário: 01/11/2019 – 13h
Local: Auditório do Bloco 910
Palestrante: Claudia Linhares Sales (MDCC/UFC)
Título: “Sistemas Brasileiros de Ensino Superior, Ciência e Tecnologia: fatos e experiências”
Resumo: “Nessa palestra, à luz da organização e estrutura do sistema de educação superior, ciência e tecnologia do Brasil, comentaremos os impasses atuais, tais como financiamento, novas políticas das agências de fomento, avaliação e medidas de qualidade, entre outros. Esses comentários serão suportados pelas experiências da palestrante como coordenadora de curso de pós-
graduação na UFC, diretora científica de fundação de amparo a pesquisa FUNCAP, pró-reitora adjunta de pós-graduação e pesquisa da UFC, membro de comitês de avaliação quadrienal da CAPES e comitê de assessoramento do CNPq, e participante ativa das sociedades científicas SBC e SBPC. Os comentários finais serão dedicados às formas de resistência e organização da comunidade científica para o enfrentamento dos atuais desafios. Cláudia Linhares Sales é professora títular da Universidade Federal do Ceará (UFC) e ocupou o cargo de Diretora Científica da FUNCAP (Fundação Cearense de Apoio ao Desenvolvimento Científico e Tecnológico) em 2010-2011 e 2012-2014. Possui mestrado em Engenharia de Sistemas e Computação pela Universidade Federal do Rio de Janeiro (1990) e doutorado em Informatique – Recherche Operationnelle – Université de Grenoble I (Scientifique Et Medicale – Joseph Fourier) (1996), sob a supervisão de Frédéric Maffray. Fez pós-doutorado no INRIA/ Sophia-Antipolis, França, entre 2006 e 2007, e na Simon Fraser University, Canadá, entre 2015 e 2016. Trabalha com Teoria dos Grafos e Algoritmos, atuando principalmente nos temas de coloração e decomposição de grafos. Ela fundou e coordena o grupo de pesquisa ParGO (Paralelismo, Grafos e Otimização), do Departamento de Computação da UFC.”

Data/horário: 25/10/2019 – 13h
Local: Sala de Seminários do 952
Palestrante: Jhonata Matias (MDCC/UFC)
Título: “The minimum maximum flow degree problem”
Resumo:“Consider a network $\Net$ with arc capacities, a sink node and a set of source nodes, where each source node has a positive integer demand to be sent from it to the sink through $\Net$. Each possible sending of the total demand that does not exceed the arc capacities defines a feasible flow. The sum of the flow entering and leaving a node $v$ of $\Net$ in a feasible flow is the flow degree of $v$. Given a feasible flow, its maximum flow degree is the maximum flow degree of the nodes of $\Net$. The minimum maximum flow degree problem (MMFDP) consists in determining in $\Net$ a feasible flow such that its maximum flow degree is minimum. The minimum maximum flow degree was initially proposed as a lower bound for the flow coloring problem. It was also used to provide an upper bound, which we improve now. Besides, we present a polynomial time algorithm for MMFDP. We also introduce a mixed integer linear program for the MMFDP and show how to solve it in polynomial time. We report results of computational experiments that compares the two proposed solution methods with another existing formulation.”

Data/horário: 18/10/2019 – 13h
Local: Sala de Seminários do 952
Palestrante: Allen Ibiapina (PGMAT/DM)
Título: “b-continuidade e colorações de Nash de grafos com cintura alta”
Resumo:“Nesse trabalho, estudamos duas variações de coloração de grafos, as $b$-colorações e as colorações de Nash. Uma $b$-coloração de um grafo $G$ é uma coloração própria $f$ tal que, para toda cor $i$, existe um vértice $v$ de cor $i$ que tem vizinhos em cada uma das outras cores. Já uma coloração de Nash é uma coloração $f$ tal que, para todo par de cores $i$, $j$ tal que $j$ possui mais vértices do que $i$, tem-se que todo vértice $i$ tem um vizinho em $j$. O número $b$-cromático (respectivamente número de Nash), denotado por $b(G)$ (respectivamente $Nn(G)$) é o maior inteiro $k$ tal que o grafo tem um $b$-coloração (respectivamente coloração de Nash) com $k$ cores. O $b$-espectro (respectivamente espectro de Nash) de um grafo é o conjunto de inteiros $k$ tais que tal grafo tem uma $b$-coloração (respectivamente coloração de Nash) com $k$ cores. Um grafo é $b$-contínuo (respectivamente Nash contínuo) quando seu $b$-espectro (respectivamente espectro de Nash) contem todo inteiro entre $\chi(G)$ e $b(G)$ (respectivamente $\chi(G)$ e $Nn(G)$).Nesta apresentação falaremos sobre os vários resultados obtidos ao longo do mestrado acerca de $b$-espectro e do Nash-espectro de grafos com cintura alta.”

Data/horário: 11/10/2019 – 13h
Local: Sala de Seminários do 952
Palestrante: Prof. Rudini Sampaio (DC/MDCC)
Título: “Mônica e Cebolinha em: “o plano infalível do jogo de coloração”.”
Slides
Resumo:“Para a Turma da Mônica decidir o dono da rua entre a Mônica e o Cebolinha, Cascão propôs em 1981 um jogo molhado para eles, chamado Jogo de Coloração em grafos. Dado um grafo G e um conjunto C de inteiros (tintas), Mônica e Cebolinha colorem vértices alternadamente (começando por Mônica) usando tintas de C de modo que vértices adjacentes recebam cores diferentes. Cebolinha vence se atrapalhar a Mônica a colorir o grafo inteiro. Em 2013, Magali propôs uma versão gulosa do problema: a cor/tinta a ser usada é sempre a menor possível. Em 1991 (28 anos atrás), Bodlaender deixou uma pergunta em aberto: Qual a complexidade do problema do Cascão? Nessa apresentação, mostramos que tanto o problema do Cascão como o da Magali são PSPACE-Completos. Apesar desse resultado negativo, Xaveco, um personagem secundário da Turma da Mônica, deixou uma pergunta secundária: Qual seria a complexidade desses problemas na classe dos grafos P4-esparsos? Nessa apresentação, mostramos que o problema guloso da Magali é polinomial; mais ainda, o número mínimo de cores é o tamanho da maior clique do grafo P4-esparso. Finalmente, Cebolinha deseja fazer um plano infalível: o que acontece se ele começar os jogos ao invés da Mônica? Ele conseguirá evitar as coelhadas do Sansão? Descubra você mesmo essa incrível historinha nesta sexta-feira às 13h.Cartunistas: Ronan Soares, Victor Lage Pessoa, Eurinardo Costa e Rudini Sampaio.”

Data/horário: 04/10/2019 – 13h
Local: Sala de Seminários do 952
Palestrante: Adriano Tavares de Freitas (MDCC)
Título: “Árvores Geradoras com Restrição de Grau Variável”
Resumo:“Considere um grafo não direcionado G=(V,E) onde o conjunto de vértices V representa nós em uma rede e o conjunto de arestas E, links de conexão entre esses nós. Considere também um conjunto S de equipamentos de transmissão que podem ser instalados nos links para viabilizar a conexão entre dois nós da rede. Para cada link {u,v} em E e para cada equipamento s em S, C(s,{u,v}) denota o custo de instalação de s em {u,v} e D(s,{u,v}) denota uma restrição de grau máximo que o equipamento s permite nas extremidades de {u,v}. Para um mesmo equipamento s, os valores C(s,{u,v}) e D(s,{u,v}) podem variar dependendo da aresta {u,v}. Essa variação pode ocorrer devido à distância entre u e v. Por conta disso, alguns equipamentos de transmissão mais simples podem não estar disponíveis para certos pares de nós. Apenas um equipamento de transmissão pode ser instalado em cada aresta e o objetivo do problema é encontrar uma árvore geradora com custo de instalação mínimo que respeite as restrições de graus nos vértices impostas pelos equipamentos instalados. O problema é NP-difícil e foi introduzido por Gouveia et al. (2014). Apresentaremos o modelo mais eficiente de Gouveia et al. (2014) para o problema e um novo modelo baseado em multigrafo, juntamente com resultados computacionais para ambos.”

Data/horário: 27/09/2019 – 13h
Local: Sala de Seminários do 952
Palestrante: Júlio Araújo (DM/PGMAT)
Título: “Some Results on Weighted Coloring”
Resumo:“Given a graph $G$ together with a weight function $w: V(G) \to \mathbb{R}^+$, a (proper) $k$-coloring of $G$ is a partition $c = \{S_1,\ldots, S_k\}$ of $V(G)$ into $k$ stable sets $S_1,\ldots, S_{k}$. The weight of a color $S_i$ is $w(i) = \max_{v \in S_i} w(v)$. The weight of a coloring $c$ is $w(c) = \sum_{i=1}^{k}w(i)$. The weighted chromatic number of a pair $(G,w)$ is $\sigma(G,w) \ = \ \min\{w(c) \mid c\text{ is a proper coloring of }G\}.$ For a positive integer $r$, we define $\sigma(G,w;r) \ = \ \min\{w(c) \mid c\text{ is a proper r-coloring of }G\}.$In this talk, we will summarize some obtained results, mostly on Parameterized Complexity, on the computation of both parameters: $\sigma(G,w;r)$ and $\sigma(G,w)$.”

Data/horário: 19/09/2019 – 13h
Local: Sala de Reuniões do 910
Palestrante: Efraim Naassom Helem Dantas Rodrigues (MDCC)
Título: “Heurísticas para coloração k-imprópria.”
Resumo:“Uma coloração dos vértices de um grafo $G = (V,E)$ é própria se vértices adjacentes recebem cores diferentes. Estudamos neste trabalho uma relaxação desse problema onde, dado um inteiro positivo $k$, é possível que um vértice e no máximo $k$ de seus vizinhos compartilhem a mesma cor. Uma vez que, como a coloração clássica, a coloração $k$-imprópria é um problema difícil, pode-se abordar o problema através do uso de heurísticas. Neste trabalho, introduzimos o número guloso $k$-impróprio de um grafo e investigamos esse parâmetro em árvores binomiais e em cografos. As definições e conceitos de $b$-coloração são generalizados para o contexto de coloração imprópria. Mostramos que a aplicação da estratégia de $b$-coloração imprópria pode não convergir. Por fim, apresentamos formulações dos problemas de coloração gulosa própria e imprópria.”

Data/horário: 13/09/2019 – 13h
Local: Sala de Seminários do 952
Palestrante: Raul Lopes (MDCC)
Título: “Adapting The Directed Grid Theorem into an FPT Algorithm.”
Resumo:“Originally proved in 1986 by Robertson and Seymour, the Grid Theorem is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in directed graphs was proved recently by Kawarabayashi and Kreutzer in 2015. In this talk, we adapt the proof of Kawarabayashi and Kreutzer into an FPT algorithm that, given a directed graph and an integer k, either finds an arboreal decomposition of width f(k) or returns a cylindrical grid of order k as a butterfly minor.”

Data/horário: 06/09/2019 – 13h
Local: Sala de Seminários do 952
Palestrante: C. Vinícius G. C. Lima (MDCC)
Título: “On the Computational Complexity of the Bipartizing Matching Problem.”
Resumo:“We study the problem of determining whether a given graph G=(V,E) admits a matching M whose removal destroys all odd cycles of G (or equivalently whether G-M is bipartite). This problem is equivalent to determine whether~$G$ admits a (2,1)-coloring, which is a 2-coloring of V(G) such that each color class induces a graph of maximum degree at most 1. We determine a dichotomy related to the NP-completeness of this problem, where we show that it is NP-complete even for 3-colorable planar graphs of maximum degree 4, while it is known that the problem can be solved in polynomial time for graphs of maximum degree at most 3. In addition we present a polynomial-time algorithm for graphs of small dominating sets and P_5-free graphs.This is joint work with Dieter Rautenbach (Ulm University, Germany), Uéverton S. Souza IC, (UFF), and Jayme L. Szwarcfiter (COPPE, UFRJ).”

Data/horário: 30/08/2019 – 13h
Local: Sala 03, bloco 914
Palestrante: Bruno Teixeira de Sousa e Paulo Henrique Sousa (UFC-Crateús)
Título: “Um Modelo de Programação Inteira Aplicado ao Problema de
Alocação de Salas da Universidade Federal do Ceará – Campus Crateús.” e “UMA ABORDAGEM HÍBRIDA EXATA-HEURÍSTICA APLICADA AO PROBLEMA DO CICLO MEDIANO SEM RESTRIÇÕES DE CAPACIDADE.”
Resumos:“O Problema da Alocação de Salas (PAS) é um clássico problema computacional que aborda a distribuição de recursos (salas e professores) visando a composição de horários escolares. Por tratar-se de um problema combinatório, classificado como NP-hard, implica a exigência de grande quantidade de recursos computacionais para sua resolução. Sabendo desta natureza e observado o gerenciamento das atividades da Universidade Federal do Ceará – Campus Crateús, um modelo computacional não linear para o referido cenário foi construído, e uma estratégia de linearização foi desenvolvida. É importante ressaltar que, no estado atual da literatura, há apenas trabalhos tratando da alocação de disciplinas ou a salas e aula ou a professores. O presente trabalho trata de ambas essas alocações. Dessa forma, experimentos computacionais com uso do algoritmo Branch and Bound (B&B) com instâncias reais e instâncias geradas através de um gerador próprio, apresentaram um aumento na complexidade para a obtenção de soluções através de programação linear inteira, salvo instâncias muito pequenas. O modelo matemático apresentou eficiência na solução do PAS, visto que todos os casos de teste resultaram em soluções viáveis.””As telecomunicações são atualmente intrínsecas ao cotidiano da maioria das pessoas, sua importância e complexidade geram custos que empresas fornecedoras desse serviço visam sempre minimizar. Uma maneira de reduzir estes custos é definindo a organização das conexões que constituem a rede utilizada. O Problema do Ciclo Mediano sem Restrições de Capacidade (PCMRC) destina-se à otimização da implantação de uma topologia anel-estrela e realiza essa tarefa através da minimização dos custos para construir sua estrutura central (ciclo) e atribuir externamente os demais elementos que não a compõem. Desta forma, o presente trabalho propõe uma abordagem híbrida aplicada ao PCMRC, um algoritmo exato-heurístico composto pelos procedimentos Branch-and-Bound (B&B), Greedy Randomized Adaptive Search Procedure e Iterated Local Search. O objetivo é encontrar uma região de soluções promissoras, usando o B\&B, para a realização de uma busca suave pela heurística. Experimentos, executados em 360 casos de testes, apresentaram resultados relevantes para esta nova abordagem.”

Data/horário: 29/08/2019 – 9h
Local: Sala de Seminários do 952
Palestrante: Rommel Dias Saraiva (MDCC)
Título: “Mathematical programming approaches for NP-Hard constrained shortest path problems.”
Resumo:“In this work, we study two NP-Hard routing problems: the shortest path with negative cycles (SPNC) and the constrained shortest path tour problem (CSPTP). For the SPNC, we propose three exact approaches based on mathematical programming: a compact mixed integer linear programming model, a specialized branch-and-bound algorithm, and a cutting-plane method. We perform numerical experiments comprising both randomly generated and benchmark instances from the literature. The computational tests show that the proposed approaches stand out from state-of-the-art mathematical programming techniques. Moreover, we discuss the linear relaxations of models present it the literature. Concerning the CSPTP, we show two compact models for the problem: a pure integer linear programming model, which we call dummy node-based model; and a mixed integer linear programming one, which we call frontier node-based model. For the latter, we show valid inequalities and propose deterministic and non-deterministic Lagrangian heuristics. Experiments performed on both randomly generated and benchmark instances from the literature validate and attest the effectiveness of our contributions, which achieve the optimal solution in the vast majority of cases. We show that the dummy node and the frontier node-based models alternate better results depending on the characteristics of each instance. The efficiency over specialized branch-and-bound algorithms from the literature is also proven through experiments, as well as the potentialities behind the Lagrangian heuristics, which find the optimal solution for a large number of instances.”

Data/horário: 23/08/2019 – 10h
Local: Sala de Seminários do 952
Palestrante: Pedro Jorge de Abreu Figueredo (MDCC)
Título: “Problema da Floresta Geradora k-Rotulada.”
Resumo:“Neste trabalho, estudamos o problema da Floresta Geradora k-Rotulada.
Dentre os problemas em grafos coloridos em arestas, neste temos como
objetivo encontrar um subgrafo gerador que é uma floresta com a menor
quantidade de componentes e com um fator limitante inteiro positivo k
para o número de rótulos distintos usados. O problema é NP-Completo, por
ser generalização do problema da Árvore Geradora Minimamente Rotulada, e
a maioria dos métodos propostos pela literatura são metaheurísticas.
Estudamos características do problema e relacionamos com a literatura
pertinente em grafos coloridos para propor três modelos matemáticos de
programação inteira mista binária e inteira binária. Propomos métodos
Branch & Cut para resolver o problema de forma exata, usando algoritmo
para separação de Cortes Coloridos. Além disso, propomos uma
paralelização para único método exato disponível na literatura, que
aplica um procedimento backtracking. Apresentamos experimentos
computacionais preliminares com os modelos e o método backtracking,
usando instâncias de teste sugeridas na literatura. Por fim, propomos
algumas melhorias para os métodos de resolução.”

Data/horário: 28/06/2019 – 14h
Local: Sala de Seminários do 952
Palestrante: Rennan Ferreira Dantas (MDCC)
Título: “Densidade mínima de Códigos de Identificação em grades.”
Resumo:“Nesta tese estudamos o Problema do Código de Identificação em grades triangulares e em king ambas infinitas. Denotamos por N[v] a vizinhança fechada de v em um grafo G e, para um conjunto C ⊆ V (G), C[v] = N [v] ∩ C. Um conjunto C ⊆ V (G) é um código de identificação em um grafo G se para todo v ∈ V (G), C[v] != ∅ e, para todos u, v ∈ V (G) distintos, C[u] != C[v]. A densidade de um código de identificação C em um grafo G é, a grosso modo, a proporção |C|/|V (G)|. A densidade mínima (ou ótima) de um código de identificação em G é denotada por d*(G) = |C*|/|V (G)|, onde C* é código de identificação de menor tamanho para G. Dado um inteiro positivo k, seja T k a grade triangular infinita com k linhas. Utilizando o Método da Descarga, determinamos a densidade mínima para Tk, com 2 ≤ k ≤ 6 e com k ≥ 7 ímpar. Determinamos também um limitante inferior e um limitante superior para d*(Tk), quando k ≥ 8 par, e conjecturamos um valor exato. Denotamos por Kk a grade king com k linhas. Novamente utilizando o Método da Descarga, determinamos a densidade mínima para Kk , com 3 ≤ k ≤ 6 e determinamos um limitante inferior e um limitante superior para d*(Kk) para todo k ≥ 7.”

Data/horário: 17/05/2019 – 14h
Local: Auditório do Bloco 910 – Mezanino
Palestrante: Victor Lage Pessoa (MMQ-DEMA)
Título: “Estudo de Complexidade de Jogos de Coloração.”
Resumo:“Respondemos nesta dissertação uma questão que permaneceu em aberto nos últimos 28 anos: a complexidade do jogo de coloração em grafos. O jogo de coloração em um grafo G simples é jogado por duas pessoas: Alice e Bob, cada um dispõe do mesmo conjunto de cores C com k cores distintas. Em turnos alternados, cada um escolhe apenas um vértice de G à ser colorido e uma cor de C de tal forma que vértices vizinhos possuam cores distintas. Alice ganha o jogo quando todos os vértices de G são propriamente coloridos e Bob ganha se em algum momento existir um vértice que não possa ser colorido com nenhuma das k cores de C. Estudamos também a complexidade de uma variante do jogo chamada de jogo de coloração gulosa e obtemos resultados para grafos da classe P4-esparso em tal jogo.”

Data/horário: 10/05/2019 – 13h
Local: Sala 3 – Bloco 914
Palestrante: Nicolas Nisse (INRIA Sophia Antipolis, França)
Título: “Recovery of disrupted airline operations using k-Maximum Matching in graphs.”
Resumo:“We study a graph theoretical problem for helping Airline Operation Controllers. Given a graph G and a matching M, the goal is to compute a maximum matching that can be achieved from M by augmenting paths of length at most k, where k is a fixed odd integer. We prove that the problem is polynomial for k at most 3. Then, we show it s NP-complete for k at least 5, in the class of planar bipartite graphs with maximum degree 3. Then, we further investigate this problem (and the other related problem where augmenting paths must have length exactly k) in trees.This is based on joint works with Julien Bensmail, Valentin Garnero, Alexandre Salchs and Valentin Weber.”

Data/horário: 06/05/2019 – 13h
Local: Sala 3 – Bloco 914
Palestrante: Julien Bensmail (Université Côte d’Azur-I3S/INRIA Sophia Antipolis, França)
Título: “A Decompositional Approach to the 1-2-3 Conjecture.”
Resumo:“The 1-2-3 Conjecture, posed in 2004 by Karonski, Luczak and Thomason, asserts that, for every connected graph dierent from K2 , we can weight its edges with weights 1; 2; 3 so that no two adjacent vertices receive the same sums of incident weights. Despite many efforts, this conjecture is still widely open to date; yet, many works towards its understanding are of interest.This talk is meant as a general introduction to the 1-2-3 Conjecture, in particular to some of the best proof techniques and tools that have been used so far. A further focus will be given to locally irregular decompositions, a particular type of edge-colouring, which were precisely introduced to deal with special cases of the 1-2-3 Conjecture. In the last part of the talk, we will present another interpretation, involving coloured weights and sums, which establishes a stronger connection between the 1-2-3 Conjecture and locally irregular decompositions.”

Data/horário: 11/03/2019 – 8h30.
Local: Sala de reuniões, bloco 910.
Palestrante: Jonas Costa Ferreira da Silva (MDCC)
Título: “Um Estudo de Redes com Fluxos Ramificados Arco-disjuntos”
Resumo:“Redes e fluxos são utilizados na modelagem de problemas de
diversos domínios diferentes, desde problemas de roteamento,
circuitos elétricos, redes de computadores até a generalização de
problemas de caminhos em digrafos.
No conceito de fluxos arco-disjuntos, não estamos interessados apenas em
encontrar um fluxo viável em uma rede, mas sim múltiplos fluxos
viáveis que sejam arco-disjuntos entre si. Essa generalização permitiu
a modelagem de novos problemas utilizando os conceitos familiares
de fluxo, desde problemas polinomiais, como o problema de decidir
se um multigrafo direcionado possui k ramificações arco-disjuntas, à
problemas NP-completos, como o problema de k-linkagem fraca.
Neste trabalho, realizamos um estudo sobre fluxos arco-disjuntos
com enfoque em fluxos ramificados, que são fluxos que possuem um
vértice fonte que envia fluxo para todos demais os vértices, de modo
que, cada um dos demais retenha uma unidade de fluxo. Tendo como
parâmetro a função de capacidade da rede, estudamos também a
complexidade do problema de encontrar fluxos ramificados arco-
disjuntos. A partir de resultados de (EDMONDS, 1973) e (BANG-
JENSEN et al., 2016), propomos uma conjectura que caracteriza
(ainda com base na função de capacidade) as redes que possuem
múltiplos fluxos ramificados arco-disjuntos e mostramos alguns casos
em que ela é válida. Além disso, introduzimos uma versão mais
restrita do problema e fazemos algumas considerações a respeito.”

Data/horário: 08/03/2019 – 13h00.
Local: Sala 03, Bloco 914.
Palestrante: Diana Sasaki Nobrega (UERJ)
Título: “Sobre problemas de coloração em grafos”
Resumo:“Os problemas de coloração em grafos modelam situações de conflito da vida real. Um destes, o problema de coloração total em grafos, é o principal foco desta apresentação. Uma coloração total de um grafo é uma atribuição de cores às arestas e aos vértices do grafo de forma que elementos adjacentes possuam cores diferentes. Estudamos o problema de determinar o menor número de cores que bastam para se colorir um grafo com uma coloração total. Apresentaremos definições importantes, o problema histórico e motivador deste tópico, bem como os principais resultados e projeções da pesquisadora.”

Data/horário: 08/03/2019 – 09h00.
Local: Sala 03, Bloco 914.
Palestrante: Pedro Paulo de Medeiros (PGMAT)
Título: “Coloração Acíclica”
Resumo:“Apresentaremos o estado da arte para uma subárea de Coloração em Grafos conhecida como Coloração Acíclica.
Dado um grafo $G$ finito, temos uma $k$-coloração acíclica de $G$ quando temos uma $k$-coloração própria para $G$ tal que quaisquer duas classes de cor induzem em $G$ uma floresta, ou seja, um subgrafo acíclico. O menor inteiro positivo $k$ tal que $G$ admite uma $k$-coloração acíclica é o número cromático acíclico de $G$, denotado por $\chi_a(G)$.
Acreditamos que este seja o primeiro texto a resumir o estado da arte para este problema, mesmo considerando outras línguas.
Apresentamos os resultados organizados por tipo. Primeiro, apresentamos aqueles relativos à limitantes para o número cromático acíclico, referentes à coloração acíclica em vértices, em arestas e coloração acíclica por listas em vértices e arestas. Em seguida, listamos os resultados referentes à complexidade computacional do problema de determinar se é possível colorir aciclicamente um grafo $G$ com $k$ cores, dados um grafo $G$ e um inteiro positivo $k$. Por fim, apresentamos problemas em aberto para a pesquisa futura.”

Data/horário: 29/02/2019 – 13h00.
Local: Sala 03, bloco 914.
Palestrante: Allen Ibiapina (PGMAT)
Título: “b-colorações e colorações de Nash em grafos com cintura alta”
Resumo:“Nessa dissertação, estudamos duas variações de coloração de grafos, as b-colorações e as colorações de Nash. Uma b-coloração de um grafo G é uma coloração f tal que, para toda cor i, existe um vértice v de cor i que tem vizinhos em cada uma das outras cores. Já uma coloração de Nash é uma coloração f tal que, para todo par de cores i,j tal que j possui mais vértices do que i, tem-se que todo vértice i tem um vizinho em j. O número b-cromático (respectivamente número de Nash), denotado por b(G) (respectivamente Nn(G)) é o maior inteiro k tal que o grafo tem um b-coloração (respectivamente coloração de Nash) com k cores. O b-espectro (respectivamente espectro de Nash) de um grafo é o conjunto de inteiros k tais que tal grafo tem uma b-coloração (respectivamente coloração de Nash) com k cores. Um grafo é b-contínuo (respectivamente Nash contínuo) quando seu b-espectro (respectivamente espectro de Nash) contem todo inteiro entre \chi(G) e b(G) (respectivamente \chi(G) e Nn(G)).Com respeito às b-colorações, provamos que todo grafo com cintura ao menos 8 é b-contínuo. Mencionamos que isso melhora o valor previamente conhecido na literatura. Além disso, demonstramos que todo grafo G com cintura pelo menos 7 é de certa forma quase b-contínuo, pois seu b-espectro contem todo valor entre 2\chi(G) e b(G).Agora, concernindo as colorações de Nash, demonstramos várias pequenas propriedades dessas colorações, em particular: provamos que, assim como as b-colorações, as colorações de Nash não são monotônicas ou contínuas; relacionamos colorações de Nash com as mais conhecidas colorações gulosas, mostrando que Nn(G) é o no máximo \Gamma(G), o número de Grundy de G; e mostramos que, sendo G desconexo, o número de Nash de G é pelo menos o número de Nash de uma de suas componentes, mas que esse limite pode ser arbitrariamente ruim. Além disso, provamos que toda árvore T é tal que Nn(T) é ao menos \Gamma(T)-1, e que é Nash contínua.”

Data/horário: 15/02/2019 – 09h00.
Local: Sala de Seminários do 952.
Palestrante: Fco. Sérgio de Freitas Filho (MDCC)
Título: “O problema da k-floresta com máximo número de folhas”
Resumo:“Dados um grafo simples conexo e um inteiro positivo k, o problema da
k-floresta com máximo número de folhas consiste em encontrar uma
floresta geradora com tantas folhas quanto possível e não mais que k
componentes. Propomos os primeiros modelos matemáticos para o problema
bem como desigualdades válidas. Para k = 1 temos o conhecido problema
da árvore geradora com máximo número de folhas (MLSTP). Em particular,
para esse problema, as novas desigualdades se mostraram muito
eficientes. Dois dos modelos propostos neste documento generalizam
formulações encontradas na literatura para o MLSTP e têm como base
formulações que descrevem os poliedros de árvores e arborescências
geradoras. Apresentamos também caracterizações para o problema, que
facilitam expressá-lo de uma maneira alternativa, onde buscamos um
conjunto de folhas que gere uma solução ótima e, uma vez que dispomos
de tal conjunto, podemos obter uma solução completa para o problema em
tempo polinomial. Como consequência, propomos um modelo denominado
(MB) o qual resolvemos utilizando um método iterativo de decomposição
de Benders para k = 1 e, para o caso geral, uma formulação denominada
(MVE) e um modelo (MFA) utilizando fluxo em rede. Realizamos
experimentos computacionais e analisamos os desempenhos dos modelos.
Em particular, para k = 1, comparamos os resultados obtidos tendo como
referência formulações da literatura para o MLSTP. Damos destaque ao
modelo (MFA) por sua simplicidade de implementação e por não demandar
técnicas sofisticadas de corte ou separação. Além disso, para k = 1,
esse modelo foi o único a encontrar soluções ótimas para todo o
conjunto de instâncias, mostrando-se superior aos modelos específicos
para o MLSTP presentes na literatura. Também vale ressaltar que, ainda
para k = 1, o modelo (MB) mostrou-se consideravelmente mais eficiente
que os demais quando consideramos um subconjunto de instâncias que
apresentam maiores densidades de arestas.”

Data/horário: 13/02/2019 – 09h00.
Local: Sala de Seminários do 952.
Palestrante: Jhonata Matias (MDCC)
Título: “Métodos para soluções do problema de fluxo fracionário”
Resumo:“Considere um grafo $G$ com uma certa demanda de fluxo a ser enviada de alguns vértices de origem a um vértice de destino. Chamamos de fluxo viável uma transmissão de fluxo através dos vértices e arestas de $G$ que satisfaz a demanda. Cada fluxo viável define um multigrafo com os vértices e arestas de $G$, mas com a multiplicidade de cada aresta sendo igual à quantidade de fluxo que passa por essa aresta no fluxo viável. Uma solução viável do problema de coloração de fluxo é composta por um fluxo viável e uma atribuição de cores às arestas do seu respectivo multigrafo tal que duas arestas adjacentes recebem cores distintas. O objetivo do problema é encontrar uma solução viável onde a coloração das arestas tenha o menor número de cores distintas. Neste trabalho, apresentamos um algoritmo aproximativo que fornece uma solução viável para o problema de coloração de fluxo com até $\lfloor (5 \chi’_\Phi + 2)/4 \rfloor$ cores, onde $\chi’_\Phi$ é o número ótimo de cores. O fator de aproximação desse algoritmo melhora o fator $3/2$ do algoritmo de Campelo et al. (2012), até então a melhor garantia de aproximação encontrada na literatura. Para esse propósito, definimos um novo problema, a ser solucionado em uma das etapas do nosso algoritmo, que provamos poder ser resolvido em tempo polinomial. Apresentamos duas novas formulações de programação inteira para o problema de coloração de fluxo, adaptamos uma terceira, proposta inicialmente para um problema relacionado, e realizamos um estudo teórico das três formulações. Propomos uma heurística, baseada no método de geração de colunas, que pode ser implementada com duas das formulações estudadas. Apresentamos experimentos computacionais realizados com as duas versões da heurística, mostrando que ambas obtêm, de forma bastante eficiente, soluções com valor muito próximo ao ótimo. Por fim, sugerimos um algoritmo exato, baseado no método de branch-and-cut, que utiliza uma das formulações estudadas e duas desigualdades que provamos serem válidas para essa formulação.”

Data/horário: 01/02/2019 – 14h00.
Local: Sala de Seminários do 952.
Palestrante: Jonas Costa Ferreira da Silva (MDCC)
Título: “Fluxos arco-disjuntos”
Resumo:“Redes e fluxos são utilizados na modelagem de problemas de
diversos domínios diferentes, desde problemas de roteamento,
circuitos elétricos, redes de computadores até a generalização de
problemas de caminhos em digrafos.
No conceito de fluxos arco-disjuntos, não estamos interessados apenas em
encontrar um fluxo viável em uma rede, mas sim múltiplos fluxos
viáveis que sejam arco-disjuntos entre si. Essa generalização permitiu
a modelagem de novos problemas utilizando os conceitos familiares
de fluxo, desde problemas polinomiais, como o problema de decidir
se um multigrafo direcionado possui k ramificações arco-disjuntas, à
problemas NP-completos, como o problema de k-linkagem fraca.
Neste trabalho, realizamos um estudo sobre fluxos arco-disjuntos
com enfoque em fluxos ramificados, que são fluxos que possuem um
vértice fonte que envia fluxo para todos demais os vértices, de modo
que, cada um dos demais retenha uma unidade de fluxo. Tendo como
parâmetro a função de capacidade da rede, estudamos também a
complexidade do problema de encontrar fluxos ramificados arco-
disjuntos. A partir de resultados de (EDMONDS, 1973) e (BANG-
JENSEN et al., 2016), propomos uma conjectura que caracteriza
(ainda com base na função de capacidade) as redes que possuem
múltiplos fluxos ramificados arco-disjuntos e mostramos alguns casos
em que ela é válida. Além disso, introduzimos uma versão mais
restrita do problema e fazemos algumas considerações a respeito.”

2018

Data/horário: 30/11/2018 – 13h00.
Local: Sala de Seminários do 952.
Palestrante: Knut Odermann (University of Chemnitz)
Título: “Extremal graphs for edge-colorings without given rainbow-colored subgraphs”
Resumo:“Given r colors and a fixed graph F, consider edge-colorings with r
colors of graphs on n vertices. In this talk we will illustrate
results with respect to edge-colorings with r colors that are free of
rainbow-colored subgraphs F, where F is a fixed complete graph. After
an introduction into this topic, we will have a quick look at the
tools that are used in the proof of such results, including
Szemerédi’s Regularity Lemma, cluster graphs and stability theorems.”

Data/horário: 23/11/2018 – 13h00.
Local: Sala de Seminários do 952.
Palestrante: Francisco Sergio de Freitas Filho (MDCC/UFC)
Título: “O problema da k-floresta com máximo número de folhas”
Resumo:“Dado um grafo simples conexo e um inteiro positivo k, o
problema da k-floresta com máximo número de folhas consiste em
encontrar uma floresta geradora com tantas folhas quanto possível e
não mais que k componentes. Propomos os primeiros modelos matemáticos
para o problema bem como desigualdades válidas. Para k = 1 temos o
conhecido problema da árvore geradora com máximo número de folhas
(MLSTP). Em particular, para esse problema, as novas desigualdades se
mostraram muito eficientes. Dois dos modelos propostos neste documento
generalizam formulações encontradas na literatura para o MLSTP e têm
como base formulações que descrevem os poliedros de árvores e
arborescências geradoras. Apresentamos também caracterizações para o
problema, que facilitam expressá-lo de uma maneira alternativa, onde
buscamos um conjunto de folhas que gere uma solução ótima e, uma vez
que dispomos de tal conjunto, podemos obter uma solução completa para
o problema em tempo polinomial. Como consequência, propomos um modelo
denominado (MB) o qual resolvemos utilizando um método iterativo de
decomposição de Benders para k = 1 e um modelo (MFA) utilizando fluxo
em rede para o caso geral. Realizamos experimentos computacionais e
analisamos os desempenhos dos modelos. Em particular, para k = 1,
comparamos os resultados obtidos tendo como referência formulações da
literatura para o MLSTP. Damos destaque ao modelo (MFA) por sua
simplicidade de implementação e por não demandar técnicas sofisticadas
de corte ou separação. Além disso, para k = 1, esse modelo foi o único
a encontrar soluções ótimas para todo o conjunto de instâncias,
mostrando-se superior aos modelos específicos para o MLSTP presentes
na literatura. Também vale ressaltar que, ainda para k = 1, o modelo
(MB) mostrou-se consideravelmente mais eficiente que os demais quando
consideramos um subconjunto de instâncias que apresentam maiores
densidades de arestas.”

Data/horário: 09/11/2018 – 14h00.
Local: Sala de Seminários do 952.
Palestrante: Paulo Henrique Macêdo de Araújo (MDCC/UFC)
Título: “The Combinatorial Classification Problem – A
Geodetic Convexity Classification Problem on Graphs”
Resumo:“Motivated by the significant advances in integer optimization in the
past decade, Bertsimas and Shioda developed a integer optimization
method to the classical statistical problem of classification in a
multidimensional space, delivering a software package called
CRIO (Classification and Regression via Integer Optimization).
Following those ideas, we define a new classification problem, exploring
its combinatorial aspects, that is defined on graphs using geodetic
convexity as a analogy of the euclidean convexity in the
multidimensional space. We call such a problem by Combinatorial
Classification Problem (CCP). We propose integer programming based
approaches for CCP along with resolution methods based on
branch-and-bound algorithms. We also show a polyhedral study of the
polyhedrons associated to each integer formulation proposed and some
valid inequalities with separation algorithms for them. Computational
experiments results and comparison between the approaches to evaluate
their combinatorial optimization efficiency are also presented.”

Data/horário: 21/09/2018 – 13h00.
Local: Sala de Seminários do 952.
Palestrante: Eurinardo R. Costa (MDCC/UFC)
Título: “Classes de Complexidade”
Resumo:“As dificuldades em resolver diversos problemas em computação estão no tempo de execução e na memória necessária para resolver o problema, além, é claro, da correção da resolução. Notou-se que os algoritmos que resolvem problemas em tempo hábil possuem complexidade de tempo polinomial, enquanto os algoritmos de complexidade de tempo exponencial demandam muito tempo, mesmo para instâncias de tamanho relativamente pequeno. Assim, para solucionar algum problema, temos o objetivo de encontrar um algoritmo com complexidade polinomial que o resolva. Contudo, há um vasto número de problemas que não se conhece resolução em tempo polinomial. Nesse cenário temos uma classificação dos problemas quanto a dificuldade de resolução. Nosso objetivo é a apresentação das principais classes de problemas estudadas na computação.”

Data/horário: 31/08/2018 – 13h00.
Local: Sala de Seminários do 952.
Palestrante: Raul Wayne Teixeira Lopes (MDCC/UFC)
Título: “Largura em árvore direcionada é FPT”
Resumo:“Parâmetros de largura em grafos podem ser vistos como uma estimativa de quão similar um grafo é de uma estrutura típica. Grafos com parâmetros de largura limitados costumam ser decompostos em partes pequenas, que são por sua vez dispostas sob um conjunto de regras e relações entre si. Assim, podemos fazer uso de técnicas clássicas de construção de algoritmos, como programação dinâmica, para resolver problemas conhecidamente difíceis em grafos com parâmetros de largura limitados. Neste trabalho, focamos na largura em árvore para grafos direcionados. Em particular, mostramos um algoritmo parametrizado, com parâmetro k, que encontra uma decomposição em árvore direcionada de largura menor ou igual a 3k-2 ou gera um certificado de que a largura é pelo menos k-1.”

Data/horário: 24/08/2018 – 13h00.
Local: Sala de Seminários do 952.
Palestrante: Arnaud Knippel (INSA/Rouen)
Título: “Combinatorics of graph Laplacian Spectra”
Resumo:“Given an undirected graph, its graph Laplacian is defined as the difference between the diagonal matrix of the node degrees and the adjacency matrix. It is a discrete analogue of the continuous Laplacian operator which is used in many physical applications with variants of the so-called wave equation. In most cases, eigenvectors are determined numerically. We are specially interested in
eigenvectors of the graph Laplacian with at least one zero component (each component is associated to a vertex of the graph), and we call lambda-soft graph a graph with such a vector [1]. We first show examples of graph transformations leading to exact results for getting eigenvectors and eigenvalues, both from the literature and from our work. We then study the special case of eigenvectors of the graph Laplacian having all their components in {-1,0,1}. The motivation comes from a recent study [2] of nonlinear dynamical systems on networks. We define three types of eigenvectors : monovalent – where all components have value 1 -, bivalent – the set of the component values is {-1,1} – and trivalent – the set of the component values is {-1,0,1}. All graphs have the monovalent eigenvector associated to the zero eigenvalue. We show that the bivalent graphs are the bipartite regular graphs and their extensions by adding any number of edges between vertices having the same value. We then call a graph soft regular for a given eigenvector of the Laplacian if all the non-zero vertices have the same degree. We show that trivalent graphs are the soft regular graphs and their extensions by some transformations. Except for special cases, finding out if a graph is bivalent or trivalent is not an easy task – yet it is still an open question if it is NP-complete.[1] Caputo, Knippel, Simo – Oscillations of networks : the role of soft nodes. Journal of Physics A, Mathematical and Theoretical (2013) [2] Caputo, Khames, Knippel, Panayotaros – Periodic orbits in nonlinear wave equations on networks. Journal of Physics A, Mathematical and Theoretical (2017) [3] Caputo, Khames, Knippel – On graph laplacian eigenvectors with components in {1,-1,0}, submitted (2018)”

Data/horário: 29/06/2018 – 13h00.
Local: Sala de Seminários do 952.
Palestrante: Walner Mendonça (IMPA)
Título: “Propriedades de Ramsey envolvendo cliques e ciclos em grafos aleatórios”
Resumo:“Um grafo G tem a propriedade de Ramsey para o par de grafos (F,H) se em toda 2-coloração das arestas de G existe uma cópia monocromática de F da cor 1 ou uma cópia monocromática de H da cor 2. Kohaykawa e Kreuter (1998) conjecturaram alguns limitantes para a probabilidade limiar da propriedade de Ramsey no modelo de grafos aleatórios de Erdős-Rényi. Eles mostraram que o limitante superior conjecturado por eles vale para alguns pares de grafos, dos quais inclui os pares (K_r,C_l), para r e l pelo menos 3. Neste trabalho, mostramos que o limitante inferior conjecturado também vale para os pares de grafos (K_r,C_l).Trabalho conjunto com Anita Liebenau (Monash Univ.), Letícia Mattos
(IMPA) e Jozef Skokan (LSE).”

Data/horário: 19/06/2018 – 14h00.
Local: Sala 03 do Bloco 914.
Palestrante: Profa. Celina de Figueiredo (COPPE-UFRJ)
Título: “Complexity-separating graph classes for vertex, edge and total colouring”
Resumo:“Given a class A of graphs and a decision problem \pi belonging to NP, we say that a full complexity dichotomy of A was obtained if one describes a partition of A into subclasses such that \pi is classified as polynomial or NP-complete when restricted to each subclass. The concept of full complexity dichotomy is particularly interesting for the investigation of NP-complete problems: as we partition a class A into NP-complete subclasses and polynomial subclasses, it becomes clearer why the problem is NP-complete in A. The class C of graphs that do not contain a cycle with a unique chord was studied by Trotignon and Vuskovic who proved a structure theorem which led to solving the vertex-colouring problem in polynomial time. We apply the structure theorem to study the complexity of edge-colouring and total-colouring, and show that even for graph classes with strong structure and powerful decompositions, the edge-colouring problem may be dicult. We discuss several surprising complexity dichotomies found in subclasses of C, and the concepts of separating problem proposed by David S. Johnson and the dual concept of separating class.”

Data/horário: 08/06/2018 – 13h00.
Local: Sala de Seminários do 952.
Palestrante: Rommel Dias Saraiva (MDCC – UFC)
Título: “Exame de qualificação de doutorado”
Resumo:“Let D=(V,A) be a loopless directed graph with set of vertices V and set of arcs A, and let each arc (i,j) in A, with i,j in V, be associated with a non-negative cost. The constrained shortest path tour problem (CSPTP) is NP-Hard and consists in finding a shortest trail between two distinct vertices s in V and t in V that visits at least one element of vertex disjoint subsets T1,T2,…,TN, in this order. We formulate the CSPTP as a mixed-integer programming (MIP) model and present valid inequalities for the problem. We also design a heuristic encapsulated within a Lagrangian framework to obtain promising feasible solutions. Computational experiments performed on both randomly generated and benchmark data sets from the literature show that our MIP model consistently dominates existing CSPTP exact algorithms. It finds optimal solutions for most instances in considerably smaller execution time with respect to other approaches.”

Data/horário: 25/05/2018 – 13h00.
Local: Sala de Reuniões do 910.
Palestrante: Allen Roossim Passos Ibiapina (PGMAT – UFC)
Título: “b-continuidade de grafos com cintura alta e resultados relacionados”
Resumo:“Uma $b$-coloração de um grafo é qualquer coloração própria onde, em cada classe de cor, existe ao menos um vértice que é adjacente a todas as outras classes de cor. Tal definição provém de um algoritmo que tenta melhorar uma coloração dada e é fácil observar que uma coloração ótima de um grafo é também uma $b$-coloração. Desta forma, o parâmetro definido é o de maximização, chamado de número $b$-cromático e representado por $b(G)$. Um aspecto interessante é que, contrário a outras variações de coloração semelhantes, nem sempre existe uma b-coloração de $G$ para todo valor entre $\chi(G)$ e $b(G)$. Se existirem, diz-se que $G$ é $b$-contínuo. Neste trabalho, o aluno melhora um resultado anterior, provando que todo grafo com cintura ao menos 8 é $b$-contínuo. Como resultado de seu lema principal, é também possível concluir que todo grafo bipartido com cintura ao menos 6 é $b$-contínuo (fechando assim o gap para bipartidos, pois existem grafos bipartidos com cintura 4) e que grafos com cintura ao menos 7 possuem $b$-colorações com $k$ cores, para todo $k$ entre $2\chi(G)$ e $b(G)$. Finalmente, foi investigado o problema de decidir se um grafo bipartido possui uma 3-$b$-coloração e provou-se que tal problema é NP-completo.Este trabalho será apresentado no III ETC (Encontro de Teoria da Computação) e no VIII LAWCG (Latin-American Workshop on Cliques in Graphs).”

Data/horário: 11/05/2018 – 13h00.
Local: Sala de Seminários do 952.
Palestrante: Álinson Xavier
Título: “Aspectos Computacionais dos Planos de Corte de Múltiplas Linhas”
Resumo:“Planos de corte são uma ferramenta essencial para a solução de problemas de Programação Linear Inteira de grande porte. Enquanto a maioria dos planos de corte utilizados atualmente na prática, incluindo os cortes de Gomory, são gerados a partir de uma única linha do tableau do método simplex, uma generalização que tem recebido bastante atenção na última década são planos de corte que só podem ser construídos a partir de múltiplas linhas do tableau. Embora a importância teórica destes cortes já tenha sido demonstrada em diversos trabalhos, continua sendo muito difícil utilizá-los na prática. Um desafio é como escolher, entre uma quantidade infinita e inumerável de possíveis cortes, um subconjunto que seja pequeno, efetivo, e que possa ser gerado rapidamente. Outro desafio vem de como fortalecer estes cortes, através de lifting, de maneira computacionalmente eficiente. Nesta apresentação, nós apresentaremos novos métodos e algoritmos relacionados a estes dois desafios.”

Data/horário: 04/05/2018 – 13h00.
Local: Sala de Seminários do 952.
Palestrante: Jonas Costa (MDCC – UFC)
Título: “Arc-disjoint branching flows”
Resumo: “The problem of determining if a given network has a feasible flow is largely studied and known to be polynomial-time solvable. In this work, we consider an specific type of flow, called branching flow, which can be useful for finding branchings in digraphs. We focus on the problem of finding multiple arc-disjoint branching flows on a given network and we study its complexity on
networks with different capacities on the arcs. A previous result shows that, under a common theoretical assumption (ETH), in networks with n vertices where all the arcs have capacity equal to n − f (n), for a bounded function f , this problem is hard. We extended this result showing that, under the same assumption, the problem is also hard when the capacities are equal to f(n).”

Data/horário: 20/04/2018 – 13h00.
Local: Sala de Seminários do 952.
Palestrante: Ronan Soares (DEMA – UFC)
Título: “LaTeX – Para que serve e como fazer um melhor uso dessa ferramenta”
Resumo:“LaTeX é uma das ferramentas mais utilizadas na publicação de artigos científicos nas áreas de ciências exatas e tecnológicas. Ele também é utilizado para preparar apresentações, notas de aula, relatórios entre outras coisas, mas será que utilizamos ele de forma “correta”? Afinal para que serve o LaTeX?Nessa apresentação, falarei um pouco sobre o LaTeX, qual o seu papel na produção de obras literárias, alternativas “viáveis” para essa ferramenta como também como evitar “erros” e produzir documentos “melhores”.”

Data/horário: 06/04/2018 – 13h00.
Local: Sala de Seminários do 952.
Palestrante: Rudini Sampaio (DC – UFC)
Título: “FPT algorithms to recognize well covered graphs”
Resumo:“Given a graph $G$, let $vc(G)$ and $vc^+(G)$ be the sizes of a minimum and a maximum minimal vertex covers, respectively. We say that $G$ is well covered if $vc(G)=vc^+(G)$ (that is, all minimal vertex covers have the same size). Deciding if a graph is well covered is coNP-complete. In this paper, we obtain $O^*(2^{vc})$-time and $O^*(1.4656^{vc^+})$-time FPT algorithms to decide well coveredness, parameterized by $vc(G)$ e $vc^+(G)$, respectively, improving results of 2015 by Boria et al. We also obtain an FPT algorithm parameterized by $\alpha(G)=n-vc(G)$ for $d$-degenerate graphs, which include bounded genus graphs (as planar graphs) and graphs with bounded maximum degree. Finally, we use the primeval decomposition technique to obtain a linear time algorithm for extended $P_4$-laden graphs and $(q,q-4)$-graphs, which is FPT parameterized by $q$, improving results of 2013 by Klein et al.This is a joint work with Sulamita Klein (UFRJ) and Rafael Teixeira (UFC).”

Data/horário: 23/03/2018 – 13h00.
Local: Sala 02 do 952.
Palestrantes: Henrique Santos de Andrade & Rodrigo Fernandes Ribeiro (DC e DM – UFC)
Títulos: “Pattern Matching in Graph Databases” & “Percolação bootstrap com condições de graus do tipo Ore e Chvátal”
Resumo 1: “Grafos estão sendo utilizados para modelar bancos de dados buscando-se obter uma modelagem mais simples e maior performance por meio de algoritmos em grafos. Diante desse modelo, surge a necessidade de realizar consultas como o Pattern Matching.Uma instância desse problema consiste em um grafo $G$, um grafo $Q$, ambos rotulados por uma função $L: V \rightarrow R$, onde $R$ é o conjunto dos rótulos dos vértices, e um parâmetro inteiro $\delta$. $G$ representa um banco de dados e pode ter milhares de vértices. $Q$ é um grafo de consulta com $n$ vértices $\left \{ v_1, …, v_n \right \}$ e tem tem uma ordem de grandeza de vértices menor que a de $G$. Além disso, ele é conexo e seus rótulos são distintos e são um subconjunto dos rótulos de $G$. O objetivo é encontrar todos os conjuntos de $n$ vértices distintos $\left \{ u_1, …, u_n \right \}$ \in G$ (Matches) tal que as seguintes condições sejam satisfeitas:$L(u_i) = L(v_j)$;Se existir uma aresta entre entre $v_i$ e $v_j$ em $Q$, o tamanho do menor caminho entre $u_i$ e $u_j$ em $G$ deve ser menor ou igual a $\delta$.Nesta apresentação, discutiremos um algoritmo para resolver esse problema e um algoritmo proposto por nós para quando o grafo de consulta $Q$ pertence a certas classes de grafos.”
Resumo 2: “A apresentação trata de problemas de infecções em grafos. Partindo de um subconjunto A dos vértices de G, definidos como os vértices inicialmente infectados, impõem-se condições sobre como a infecção se espalha para os demais vértices, o que define o modelo a ser estudado. O modelo principal dissecado é conhecido como “percolação bootstrap de r-vizinhança” e, nele, novos vértices tornam-se infectados em um dado instante se eles possuem pelo menos r vizinhos já infectados no instante anterior, ao passo que, uma vez infectado, um vértice permanece infectado.Formalmente, seja A_0=A e, para t natural, define-se A_{t+1} como a união de A_t com o conjunto dos vértices que possuem pelo menos r vizinhos em A_t. Se existir t tal que A_t = V, dizemos que A é r-contagioso. Focamos no problema de, dados G e r, determinar o menor número, m(G,r), de vértices de um conjunto r-contagioso. Em particular, nos resultados de 2 artigos recentes: um de Dairyko, Ferrara, Lidický, Martin, Pfender e Uzzell, e outro de Freund, Poloczek e Reichman. Ambos dão condições suficientes sobre G para que m(G,2) seja 2, envolvendo a soma dos números de vizinhos de pares de vértices não adjacentes, de modo semelhante ao teorema de Ore e Chvatal.”

Data/horário: 09/03/2018 – 13h00.
Local: Sala de Seminários do 952.
Palestrante: Rennan Dantas (DC – UFC)
Título: Exame de Qualificação de Doutorado
Resumo:“Vou falar sobre a caracterização dos grafos split, de permutação, de intervalo e limiares. Falarei também sobre algumas diferenças e similaridades entre essas classes de grafos e sobre alguns resultados do Problema do Código de Identificação nessas classes de grafos.”

2017

Data/horário: 01/12/2017 – 13h00.
Local: Sala de Seminários do 952.
Palestrantes: Gabriel Hellen de Sousa & Isnard Lopes (DEMA e DMAT – UFC)
Títulos: “Métodos para determinação do número de envoltória de um grafo” & “Solução do Problema da T-join Mínima por meio de redução ao Problema de Emparelhamento Perfeito de Peso Mínimo”
Resumo 1: “O número de envoltória (hull number) de um grafo G = (V,E) não-orientado, onde V é o conjunto de vértices e E, o conjunto de arestas, consiste no menor número de vértices que, inicialmente contaminados, conseguem, iterativamente, contaminar todo o grafo. O principal tipo de contaminação estudada neste trabalho foi a geodésica, em que, dados dois vértices contaminados, todos aqueles em qualquer caminho mínimo entre os dois estarão contaminados na próxima iteração. Determinar o número de envoltória geodésica é um problema NP-Difícil, mesmo para classes de grafos como bipartidos. Neste trabalho, foram estudados e implementados dois modelos matemáticos e uma heurística para o problema. Para resolução dos modelos utilizou-se o solver CPLEX
acoplado à linguagem de programação C++, e para a heurística utilizou-se uma implementação na mesma linguagem. Os grafos usados como instâncias de teste foram, em sua maioria, bipartidos, gerados aleatoriamente, a partir de dois parâmetros: quantidade de vértices e um fator de probabilidade para definir a existência das arestas. Os resultados que cada método apresentou, referentes ao tempo de execução e à solução, foram armazenados e comparados, para se determinar a eficiência dos modelos e a precisão da heurística. O primeiro modelo, denominado passo-de-contaminação, mostrou-se mais lento, computacionalmente, que o segundo, chamado co-convexo, na maior parte dos testes. A heurística mostrou um menor desvio da solução ótima em grafos com alta densidade de arestas, encontrando a melhor solução em quase todos os testes.”
Resumo 2: “Seja G = V, E um grafo e seja T um subconjunto par de V. Um subconjunto H de arestas de E(G) é chamado T − join quando |δ(v)| ≡ 1 mod 2 , se v ∈ T; ≡ 0(mod 2), se v ∈ V|T. Um problema muito famoso em Teoria dos grafos é o Problema do Carteiro Chinês que recebeu esse nome depois que o matemático chinês, Kwan Mei-Ko, o descobriu no início dos anos 1960, que tem o seguinte enunciado: “Um carteiro apanha, na agência de correios, algumas correspondências, as entrega e retorna à agência. De forma que ele deseja traçar uma rota tal que seu custo seja o mínimo possível”. O problema acima é bem similar ao Problema das Sete Pontes de Königsberg, resolvida por Leonhard Euler (1707-1782) – que deu início ao ramo da Teoria dos Grafos em Matemática – e é um problema de T − join, que é um caso particular do seguinte problema: PROBLEMA DA T-JOIN PONDERADA DADOS: um grafo ponderado G ∶= G, w e um subconjunto T de V, ENCONTRAR: uma T − join de peso mínimo em G (caso exista). É muito comum na Teoria dos Grafos reduzirmos determinados problemas a outros mais fáceis de resolver. Mostraremos que o problema destacado acima pode ser facilmente reduzido a um problema de emparelhamento, a saber: PROBLEMA DO EMPARELHAMENTO DE PESO MÍNIMO DADO: um grafo ponderado completo G ∶= G, w de ordem par, ENCONTRAR: um emparelhamento perfeito de peso mínimo em G.”

Data/horário: 24/11/2017 – 13h00.
Local: Sala de Seminários do 952.
Palestrantes: Pedro Arraes & Camila Araujo (Dep. Mat. – UFC)
Títulos: “Convexidade em grafos orientados” & “Colorações Backbone”
Resumo 1: “O tema da apresentação será convexidade em grafos direcionados, focando no conjunto fechante e no número de fecho. Basicamente, um grafo direcionado D = (V,A) é composto por um conjunto de vértices V e um de arcos A, tais que cada arco é associado a um par ordenado de vértices. Para simplificar a análise dos casos, trabalhamos com grafos direcionados simples: cada arco é associado a um par ordenados de vértices distintos e não existem duas arestas associadas ao mesmo par de vértices(mesmo se a ordenação for diferente). Dado um grafo direcionado D = (V,A), sejam u,v pertencentes a V. Um (u,v)-geodésico é um caminho de u até v com a menor quantidade de vértices possível. Sendo S um subconjunto arbitrário de V e P(V) o conjunto das partes de V, a função de intervalo I: P(V) -> P(V) aplicada em S retorna o conjunto I[S], composto pelos vértices de S e pelos que estão em algum (u,v)-geodésico ou em algum (v,u)-geodésico tais que u,v pertencem a S. Se aplicarmos essa função iterativamente em S(In[S] = I[In-1[S]] = I[I[…I[S]…]]), obteremos um conjunto [S] = In[S], para algum n natural, tal que In+1[S] = I[In[S]] = I[[S]] = [S]; esse é chamado de fecho convexo de S. Caso [S] = V, S é dito um conjunto fechante de D. Quando S é um conjunto fechante com a menor quantidade de elementos possível, temos que o número de fecho de D é a cardinalidade de S, hn(D) = |S|. Na apresentação, mostraremos um algoritmo para obter um conjunto fechante com cardinalidade mínima na classe de grafos cactos direcionados, além do nosso progresso em provar que o problema do número de fecho é NP-difícil para a classe de grafos bipartidos direcionados.”
Resumo 2: “Um grafo G=(V,E) é uma estrutura matemática formada por um conjunto de vértices V(G) e um subconjunto E(G) de pares não ordenados de V(G), denominados arestas. Quando (u,v)=uv pertence ao E(G), dizemos que u e v são adjacentes. Um subgrafo de um grafo G é um grafo no qual V(H) está contido em V(G) e E(H) está contido em E(G). Sejam G um grafo e H um subgrafo de G, dizemos que (G,H) é um par, onde H é chamado backbone de G. Uma k-coloração de vértices de um grafo G é uma função c: V(G)->{1,2,…,k}, na qual o valor c(v) será chamado de cor de v em c. Dizemos que uma coloração é própria se |c(u)-c(v)|>0, sempre que uv pertence ao E(G). O problema clássico de Coloração de Vértices trata-se de se determinar o número cromático de um dado grafo, que corresponde ao menor inteiro k para o qual existe uma coloração própria utilizando apenas k cores. Neste trabalho, estudamos uma variação do problema de coloração em vértices de um grafo, conhecida por Coloração Backbone. Uma k-coloração q-backbone de (G,H) é uma função f: V(G)->{1,…,k} tal que f é uma coloração própria sobre os vértices de G e, além disso, as cores atribuídas a vértices adjacentes em H diferem de, pelo menos, q. Denotaremos por BBCq(G,H) o menor número inteiro k para o qual existe uma coloração q-backbone que utilize apenas k cores. Os resultados estudados e obtidos durante o projeto, estão relacionados com o valor BBCq(G,H) sob o ponto de vista de otimização, buscando um limitante superior de BBCq(G,H) quando G e H pertencem a uma determinada classe de grafos.”

Data/horário: 20/10/2017 – 14h00.
Local: 914, sala 03.
Palestrante: Matthew Jenssen (London School of Economics and Political Science)
Título: “On the hard sphere model and sphere packings in high dimensions.”
Resumo: “We provide a statistical physics based proof of the $\Omega(d \cdot 2^{-d})$ lower bound on the sphere packing density of $\mathbb{R}^d$. Such a bound on the sphere packing density was first achieved by Rogers, with subsequent improvements to the leading constant by Davenport and Rogers, Ball, Vance, and Venkatesh. While our technique does not achieve the same constant as these other proofs, we do obtain additional probabilistic and geometric information: we lower bound the expected packing density of a random configuration from the hard sphere model and lower bound the \emph{entropy} of sphere packings of density $\Theta(d \cdot 2^{-d})$, a measure of how plentiful such packings are. This is joint work with Will Perkins and Felix Joos.”

Data/horário: 06/10/2017 – 13h00.
Local: 952, sala de seminários.
Palestrante: Cláudia Linhares Sales (DC/UFC)
Título: “b-colorings: an structural overview”
Resumo:“A $b$-coloring of a graph $G$ is a proper coloring such that every color class has a vertex with neighbors in each other color class. The $b$-chromatic number of $G$ is the maximum integer $k$ such that $G$ admits a $b$-coloring with $k$ colors. This parameter was introduced by Irving and Manlove in 1999. In that work, they proved that the related decision problem is $NP$-complete while polynomial on trees. In this talk, we start by relating the $b$-chromatic number of $G$ with its other chromatic numbers issued of other heuristics. Then, we recall some structural properties of graphs which directly impact their $b$-chromatic number and other related parameters, such as girth, maximum degree, $m$-degree and forbidden subgraphs. In particular, we are going to see how the good structural behavior of product of graphs impact some parameters related to $b$-colorings. We finish this talk by showing two recently defined $b$-colorings parameters, namely $b$-homomorphism and partial $b$-coloring and some of their open problems of general interest.”

Data/horário: 26/09/2017 – 14h30.
Local: 952, sala de seminários.
Palestrante: Igor Machado Coelho (IME/UERJ)
Título: “Aplicações de GPU em heurísticas de otimização”
Resumo:“Arquiteturas emergentes de computação tem demonstrado um forte crescimento nos últimos anos, atingindo a marca de TeraFlops de processamento. Tais dispositivos, como as Graphics Processing Units (GPUs), conseguem aliar alto poder computacional com um baixo consumo de energia, se tornando opções bastante acessíveis para o desenvolvimento de novos algoritmos que necessitam de alto poder computacional. Diversos problemas de otimização combinatória são encontrados no nosso cotidiano, por exemplo ao montar uma grade eficiente de aulas em um curso de graduação, ou simplesmente tentar encontrar uma rota para entregas de produtos que minimize a distância total percorrida. Embora sejam muito comuns, muitos destes problemas são tidos como intratáveis, onde nenhum algoritmo de tempo polinomial que possa resolvê-los na otimalidade é conhecido. Neste contexto usualmente são empregados arcabouços heurísticos de uso geral, ou metaheurísticas, que muitas vezes são inspirados em fenômenos da natureza, e embora não garantam a otimalidade da solução encontrada, na prática conseguem resolver problemas de grande porte com um tempo computacional razoável. Esta palestra se destina a apresentar os últimos trabalhos desenvolvidos que buscam integrar estratégias metaheurísticas com arquiteturas de computação em alta performance.”

Data/horário: 22/09/2017 – 13:00h.
Local: 952, sala 02.
Palestrante: Rafael Castro (DEMA/UFC)
Título: “Modelos do polytopo de árvore geradora”
Resumo:“Discutiremos resultados para o polytopo da árvore geradora com foco em formulações de programação inteira cuja relaxação linear é inteira. Mostramos que o modelo da árvore geradora de Martin, quando usado para grafos direcionados, pode dar soluções com ciclos de tamanho dois. Mostramos também que uma interpretação correta e uma redefinição das variáveis de decisão desse modelo de Martin permite resolver esse problema, ao mesmo tempo em que ele se estende para multigrafo geral, completo ou
não, direcionado ou não, considerando múltiplas arestas (ou arcos) entre qualquer par de nós. O modelo extendido compacto resultante generaliza o politopo de florestas.”

Data/horário: 01/09/2017 – 13:00h.
Local: 952, sala 02.
Palestrante: Manoel Campêlo (DEMA/UFC)
Título: “O problema de alocação conexa em vetores”
Resumo:“Definimos o problema de alocação conexa em vetores, a partir de uma aplicação em redes de telefonia móvel 4G. Dado um vetor com N posições e um conjunto de M símbolos, queremos preencher o vetor com um subconjunto desses símbolos, de modo que símbolos repetidos apareçam consecutivamente no vetor, maximizando o ganho total da alocação (a alocação de um símbolo i em uma posição j fornece um ganho de $\rho_{ij}\geq 0$).No contexto da aplicação, um dos desafios é fornecer uma boa solução para esse problema NP-Difícil em menos de 1ms. Nesse sentido, apresentamos 04 heurísticas, baseadas em diferentes estratégias, e as avaliamos computacionalmente com instâncias de testes geradas a partir de um simulador de tráfego real. Consideramos também instâncias geradas aleatoriamente. Na perspectiva de revolver o problema de forma exata, descrevemos parcialmente o politipo associado ao problema. Mostramos todas as classes de desigualdades indutoras de facetas com coeficientes binários. Mostramos que elas são suficientes para descrever completamente o politopo quanto M=2 ou N=2.”

Data/horário: 25/08/2017 – 13:00h.
Local: 952, sala 02.
Palestrante: Júlio Araújo (DM/UFC)
Título: “Hull and interval numbers in Cycle Convexity”
Resumo:“Due to a motivation in Knot Theory, a new graph convexity, that we call Cycle Convexity, has been recently defined. In this convexity space, a set of vertices S of a graph G is convex if every vertex that is not in C has at most one neighbor in each component of G[S].In this talk, we will present such graph convexity and the results we so far obtained for the parameters hull and interval numbers in this new convexity.Joint works with V. Campos, D. Girão, J. Nogueira, A. Salgueiro and A. Silva and G. Ducoffe, N. Nisse and K. Suchan.”

Data/horário: 07/07/2017 – 13:00h.
Local: 952, sala de seminários.
Palestrante: Ângelo Brayner (DC/UFC)
Título: “Database Technology + Graph Theory: Towards High Performance.”
Resumo: “O volume de dados produzidos tem aumentado exponencialmente. Prevê-se que, por volta de 2020, p volume de dados armazenados será em torno de 40 trilhões de GB, uma tava de 5.200 GB por pessoa. Em torno de 90% dos dados armazenados atualmente são gerenciados através de técnicas implementadas pela tecnologia de Banco de Dados. Uma das grandes limitações da tecnologia de banco de dados é a implementação de relacionamentos entre os dados. Para superar esta limitação, surgiu a proposta de banco de dados implementados através de grafos (graph databases), onde dados e relacionamentos são representados através de nós e arestas de um grafo. Nesta apresentação, discutiremos esta nova abordagem, com o objetivo de identificarmos oportunidades de aplicação de algoritmos de grafos, para solucionar problemas neste novo tipo de banco de dados.”

Data/horário: 22/06/2017 – 13:00h.
Local: 952, sala de seminários.
Palestrante: Ignasi Sau Valls (DEPMAT/LIRMM)
Título: “Finding subdivisions of spindles on digraphs.”
Resumo: “For two positive integers $k$ and $\ell$, a $(k \times \ell)$-spindle is the union of $k$ pairwise internally vertex-disjoint directed paths with $\ell$ arcs between two vertices $u$ and $v$. In this talk we are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems.We obtain the following complexity dichotomy: for a fixed $\ell \geq 1$, finding the largest $k$ such that an input digraph $G$ contains a subdivision of a $(k \times \ell)$-spindle is polynomial-time solvable if $\ell \leq 3$, and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and prove several positive and negative results.Joint work with Júlio Araújo, Victor A. Campos, Ana Karolinna Maia, and Ana Silva.”

Data/horário: 09/06/2017 – 13:00h.
Local: 952, sala de seminários.
Palestrante: Antonio Josefran Oliveira Bastos
Título: “Densidade de empacotamento e a densidade mínima de subsequências monótonas em permutações em camadas.”
Resumo:“Sejam $\pi$ e $\sigma$ permutações. Dizemos que a permutação $\pi$ ocorre na permutação sigma se existe uma subsequência de tamanho $|\pi|$ de elementos de $\sigma$ que possui a mesma ordem relativa entre seus elementos que a permutação $\pi$. Denotamos por $p(\pi, \sigma)$ a probabilidade de sortearmos uniformemente ao acaso uma subsequência em $\sigma$ com tal propriedade. Dado um inteiro $n > 0$, seja $S_n$ o conjunto de todas as permutações de tamanho $n$. Uma questão natural é analisar qual o maior valor que $p(\pi, \sigma)$ pode atingir dentre todas as permutações em $\sigma \in S_n$. O valor $p(\pi) = \lim_{n \to \infty}\max_{\sigma \in S_n}p(\pi, \sigma)$ é chamado de valor de empacotamento de $\pi$ e descobrir este valor, assim como a sequência de permutações $(\sigma_n)_{n \in \mathbb{n}}$ que atinge este valor, é conhecido como o Problema de Empacotamento em Permutações. Apesar de parecer simples, ainda existem permutações de tamanho 4 para qual se desconhece o valor de empacotamento. H\”{a}st\”{o} calculou com exatidão o valor de empacotamento para permutações pertencentes a um subconjunto de permutações em camadas (permutações que são construídas através da junção de sequências continuas decrescentes formando uma sequência crescente de subsequências decrescentes, por exemplo a permutação 214365). No primeiro resultado apresentado neste seminário, generalizamos o resultado de H\”{a}st\”{o} para abranger um conjunto maior de permutações em camadas.Outra questão que surge relacionado ao estudo da função $p$ é saber qual a permutação que realiza o mínimo. Note que se estamos interessados em minimizar $p$ relacionado a um única permutação então o problema se torna trivial. Porém, o problema se torna desafiador se tentarmos minimizar o total de ocorrências de mais de uma permutação. Sejam $k, \ell > 0$ inteiros positivos. Denotamos por $\Id_\ell$ a permutação identidade de tamanho $\ell$ e por $\Rev_k$ a permutação reversão de tamanho $k$. Myers conjecturou que para todo $n > 0$ a permutação em $S_n$ que minimiza o total de ocorrência de $\Id_\ell$ e $\Rev_k$ pode ser obtida restringindo nosso conjunto de busca ao conjunto de todas as permutações que não contém $\Id_\ell$ ou $\Rev_k$. A Conjectura de Myers já está aberta a mais de 15 anos e diversos avanços foram feitos. Em 2013, utilizando Flag Algebras Balogh et al determinaram que a Conjectura de Myers é verdadeira para $\ell = k = 3$. No segundo resultado apresentado neste seminário, mostramos que se $k \geq \ell \geq 3$ e restringirmos o conjunto de busca $S_n$ ao conjunto de permutações em camadas então a Conjectura de Myers é verdade.O trabalho apresentado neste seminário foi realizado em conjunto com Leonardo Nagami.”

Data/horário: 12/05/2017 – 13:00h.
Local: 952, sala de seminários.
Palestrante: Allen Roossim Passos Ibiapina (PGMAT-UFC)
Título: “Coloração ortogonal de arestas e o Teorema das 4 cores.”
Resumo:“Em 1878, Tait provou a equivalência entre o Problema das 4 cores e o problema de colorir as arestas de um grafo planar cúbico com 3 cores. Ele achou na verdade ter encontrado uma prova para o referido problema, o que posteriormente foi observado estar incorreta. Os contra-exemplos para a prova de Tait, o primeiro tendo sido o famoso grafo de Petersen, são objetos raros na natureza e por isso foram apelidados de snarks, criatura elusiva de que trata um poema de Lewis Carrol. Nesta apresentação, iremos explorar estes conceitos, relacionando-os a um outro tipo de coloração, chamada de coloração ortogonal.”

Data/horário: 05/05/2017 – 13:00h.
Local: 952, sala de seminários.
Palestrante: Nicolas de Almeida Martins (MDCC-UFC)
Título: “Jogos de Perseguição em Grafos e Coloração Localmente Identificável (Proposta de doutorado)”
Resumo:“Nesta tese estudamos os problemas de coloração localmente identificável (lid-coloração) e diversos parâmetros relacionados a jogos de perseguição em grafos.Para colorações localmente identificáveis, mostramos que o número lid-cromático e o número lid-cromático forte são ambos $O(n^{\frac{1}{2}-\varepsilon})$-inaproximáveis em tempo polinomial, a menos que $P=NP$, bem como algoritmos lineares para $(q,q-4)$-grafos e para grafos com largura em árvore limitada para ambos os parâmetros.Com relação a jogos de perseguição, estudamos dois jogos diferentes: Jogo de Polícia e Ladrão e o Jogo do Espião. Para o Jogo de Polícia e Ladrão mostramos valores exatos para o cop-number e o $k$-capture time de grafos $P_4$-tidy. Além disso mostramos que a famosa conjectura de Meyniel é válida para grafos $P_4$-tidy conexos e $(q,q-4)$-grafos conexos com pelo menos de $q^2$ vértices.O Jogo do Espião foi introduzido recentemente por N. Nisse. Mostramos que esse problema é NP-difícil para qualquer velocidade $s\geq 2$ do espião e qualquer distância $d\geq 0$ para os guardas e, além disso, $(1-o(1)) \ln n$-inaproximável em tempo polinomial, a menos que $P=NP$. Ademais, mostramos limites superiores para um dos parâmetros do jogo para ciclos e caminhos e provamos que a versão direcionada do problema é PSPACE-difícil para DAG’s.”

Data/horário: 12/04/2017 – 13:00h.
Local: 952, sala de seminários.
Palestrante: Ana Karolinna Maia (DC-UFC)
Título: “Detecting subdivisions in digraphs”
Resumo:“In this work, we consider the following problem: Given a directed graph
D, does it contain a subdivision of a prescribed digraph F? We believe that there
is a dichotomy between NP-complete and polynomial-time solvable instances of this problem. We present many examples of both cases. In particular, except for five instances, we are able to classify all the digraphs F of order 4.While all NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, we use different algorithmic tools for proving polynomial-time solvability of certain instances, some of them involving relatively complicated algorithms. The techniques vary from easy brute force algorithms, algorithms based on maximum-flow calculations, handle decompositions of strongly connected digraphs, among others.”

Data/horário: 24/03/2017 – 13:00h.
Local: 952, sala de seminários.
Palestrantes: Calos Abraão (DEMA) e Arthur Walraven (DEPMAT)
Títulos: “Uma Implementação do problema de fluxo máximo com restrições de conflito” e “Bootstrap percolation por grafos”
Resumos:“Neste trabalho nós estudamos o problema de fluxo máximo, em um grafo direcionado, acrescido de restrições binárias de conflito. Uma restrição de conflito determina que, para um certo par de arcos, seus elementos não podem ser utilizados simultaneamente numa solução viável. Para representar essas restrições, nós temos um grafo de conflito, onde seus vértices correspondem aos arcos do grafo original e cada aresta representa uma restrição entre os vértices(arcos) associados. Usamos como base o trabalho de Pferschy & Schauer (2013), no qual prova-se que o problema de fluxo máximo com restrições de conflito é NP-difícil. Implementamos uma formulação de programação matemática para o problema, usando o software CPLEX da IBM. Para realizar experimentos computacionais, criamos um gerador de instâncias, descritas pelo grafo direcionado, sobre o qual o fluxo será enviado, e pelo grafo de conflitos, que descreve as restrições correspondentes. Realizamos testes variando as densidades de ambos os grafos, e o tempo aumentou gradualmente de acordo com a densidade do grafo de conflitos. No entanto quando a densidade do grafo de conflitos é elevada o solver começa a retornar a solução de maneira mais rápida.””Na percolação bootstrap, dado um grafo H e um conjunto G ⊆ E(Kn), adiciona-se iterativamente ao último toda aresta que complete uma nova cópia de H em G. O processo termina quando não existem mais arestas que atendam tal critério. Na apresentação, iremos discorrer sobre o uso de técnicas probabilísticas para analisar o comportamento do tempo máximo de execução do algoritmo quando H = Kr.”

Data/horário: 16/02/2017 – 14:00h.
Local: 952, sala de seminários.
Palestrante: Thiago Marcilon (Doutorando em Ciência da Computação, MDCC) – Defesa de Tese
Título: Resultados no Tempo Máximo e no Número de Envoltória nas Convexidades $P_3$ e Geodésica
Resumo:Convexidade em grafos é um conceito inspirado na convexidade da geometria euclidiana e vem sendo bastante explorado nas últimas décadas. Muitas aplicações reais como a difusão de uma infecção ou de informação em uma rede social podem ser modeladas usando alguma convexidade em grafos baseada em caminhos do grafo. Nesta tese, nós abordamos dois problemas computacionais relacionados à convexidade em grafos: Número de Envoltória e Tempo Máximo de Infecção. Fixada uma convexidade C, o problema Número de Envoltória consiste em, dados um grafo G e inteiro k, determinar se o número de envoltória de G na convexidade C é no máximo k. O problema Tempo Máximo de Infecção consiste em, dados um grafo G e inteiro k, determinar se o tempo máximo de infecção de G na convexidade C é no mínimo k. Apresentamos algoritmos polinomiais para o problema Tempo Máximo de Infecção na convexidade P3 em algumas classes de grafos e para k fixo. Apresentamos também algoritmos tratáveis em parâmetro fixo na combinação dos parâmetros grau máximo do grafo e k e na combinação dos parâmetros largura em árvore do grafo e k. Também apresentamos resultados de NP-completude para o problema Tempo Máximo de Infecção na convexidade P3 em algumas classes de grafos e para algumas restrições da entrada k. Apresentamos ainda a sua W[1]-dificuldade para o parâmetro largura em árvore. Finalmente, mostramos que o problema Número de Envoltória na convexidade P3 é W[1]-difícil no parâmetro k em grafos livres de K3 com grau máximo seis. Mostramos também que o problema Número de Envoltória na convexidade geodésica é W[1]-difícil no parâmetro k em grafos com diâmetro dois e na combinação dos parâmetros largura em árvore e k. Apresentamos ainda um algoritmo XP no parâmetro largura em árvore que calcula o número de envoltória de um grafo na convexidade geodésica.

2016

Data/horário: 09/12/2016 – 10:00h.
Local: 952, sala 02.
Palestrante: Thiago Marcilon (Doutorando em Ciência da Computação, MDCC)
Título: Resultados no Tempo Máximo e no Número de Envoltória nas Convexidades $P_3$ e Geodésica
Resumo:Convexidade em grafos é um conceito inspirado na convexidade da geometria Euclidiana e vem sendo bastante explorado nas últimas décadas. Convexidade em grafos modela várias aplicações reais como a difusão de uma infecção e informação em uma rede de pessoas.Abordaremos dois problemas computacionais relacionados à convexidade em grafos: Número de Envoltória e Tempo Máximo de Infecção.Conseguimos resultados de $\mathbf{NP}$-completude na complexidade $P_3$ para grafos grade e bipartidos para $k$ fixo para o problema Tempo Máximo de Infecção e de $W[1]$-dificuldade nas convexidades $P_3$ e geodésica para os problemas Número de Envoltória e Tempo Máximo de Infecção em diversos parâmetros. Também conseguimos algoritmos polinomiais para Tempo Máximo de Infecção na convexidade $P_3$ em algumas classes de grafos e para $k$ fixo e algoritmos tratáveis em parâmetro fixo para Número de Envoltória na convexidade geodética no parâmetro largura em árvore. Destes resultados, apresentaremos o algoritmo para o Tempo Máximo de Infecção na convexidade $P_3$ em grafos bipartidos para $k=3$ e a $W[1]$-dificuldade do Número de Envoltória nas convexidades $P_3$ e geodésica no parâmetro $k$.

Data/horário: 02/12/2016 – 16:00h.
Local: 952, sala 02.
Palestrante: Lucas de Sousa Fernandes e Lucas Primo Fernandes Muraro (Departamento de Computação, UFC)
Título: (Arc-)disjoint flows in networks
Resumo:In this work, Jørgen Bang-Jensen and Stéphane Bessy consider the problem of deciding whether a given network with integer capacities has two feasible flows $f$ and $g$ with prescribed balance vectors such that the arcs that carry flow in $f$ are arc-disjoint from the arcs that carry flow in $g$. This generalizes a number of well-studied problems such as the existence of arc-disjoint out-branchings $B_s^{+}$ , $B_t^{+}$ where $s=t$, etc. Hence the problem is NP-complete in general. They show that the problem remains hard even for very restricted cases such as two arc-disjoint. They also show that the property of the existence of a spanning connected eulerian subdigraph is NP-complete to decide.

Data/horário: 25/11/2016 – 16:00h.
Local: 952, sala de seminários.
Palestrante: Julien Baste (Université de Montpellier, LIRMM, Montpellier, France)
Título: Linear contraction exclusion of triangulated grids
Resumo:It was shown that there exists a function f: N->N such that any graph excluding a (k x k)-grid as a minor has treewidth at most f(k). It was also shown that if a graph G excludes the triangulated grid, which we name $\Gamma_k$, as a contraction, then the treewidth of G is at most f(2k+1). The current best upper bound is $f(k) = k^{19} polylog(k)$. In this talk we focus on classes of graphs for which the bidimentionality theory applies, i.e., $f(k) = O(k^c)$ for some fixed c with $1 <= c<2$, and we say that these classes of graphs have the gamma contraction property.We consider geometric intersection graphs where each body of the collection is represented by a vertex, and two vertices are adjacent if the intersection of the corresponding bodies is non-empty. In this talk, we show that the restriction of this class of graphs to the graphs of bounded degree has the gamma contraction property. Our results extend the applicability of bidimensionality theory for contraction-closed parameters.Joint work with Dimitrios M.Thilikos.

Data/horário: 24/11/2016 – 16:00h.
Local: 952, sala de seminários.
Palestrante: Prof. Daniel Severin (Universidad Nacional de Rosario)
Título: Cross-identification of stellar catalogs with multiple stars
Resumo: In the science of astronomy, it is common to record the position and other physical quantities of stellar objects in astronomical catalogs. They are of extreme importance for various disciplines, such as navigation, space research and geodesy, and there is a major international effort to improve the quality of these data permanently. In particular, there exist several star catalogs where one can query the position, brightness, spectrum, etc, of a given star. Naturally, a single star has different designations according to the catalog being used that uniquely identifies in it, and therefore, there is an overriding need to know the (most probable) designation of a star in a catalog given its designation in other one. This optimization problem is known as the cross-identification problem. However, a new problem arises when one entry of a stellar catalog correspond to multiple entries of another catalog. Let us consider two catalogs A and B, where each star a of catalog A has an extra parameter k_a denoting its cardinality. The problem consists of assigning k_a stars of catalog B to each star a of A, in such a way the probability of the assignment is maximized. In this talk, both problems and their resolutions are presented.

Data/horário: 04/11/2016 – 16:00h.
Local: 952, sala 02.
Palestrante: Camila Sena (Departamento de Matemática, UFC)
Título: Backbone Colorings: on matching of outerplanar graphs
Resumo:Given a graph $G$ and a subgraph $H$ of $G$, a $q$-backbone $k$-coloring of $(G,H)$ is a (proper) $k$-coloring $\phi$ of $G$ such that $|\phi(u)-\phi(v)|\geq{q}$, for every edge $uv\in{E(H)}$.The q-backbone chromatic number of $(G,H)$, denoted by $BBC_q(G,H)$, is the minimum integer $k$ for wich there exists a q-backbone k-coloring of $(G,H)$.It is proved for Broersma et al. (2007) that $BBC_{\lambda}(G,M)\leq{2\chi(G)-2}$, for $\lambda+1\leq{\chi(G)}\leq{2\lambda}$, where $M$ is a matching of $G$. This yields, by the Four Color Theorem, that $BBC_2(G,M)\leq{6}$, for any planar graph $G$. The latter implies that $BBC_2(G,M)\leq{5}$, for any outerplanar graph $G$.It is not known a proof of $BBC_2(G,M)\leq{6}$, for any planar graph $G$, that does not require the Four Color Theorem and it is not known any graph where the equality is satisfied. This allows us to ask ourselves if $BBC_2(G,M)\leq{5}$ holds for any planar graph $G$ with a matching backbone $M$. The latter would imply that $BBC_2(G,M)\leq{4}$, for any outerplanar graph $G$.In this work, we proved that $BBC_2(G,M)\leq{4}$ for any outerplanar graph without $C_4$.

Data/horário: 04/11/2016 – 16:00h.
Local: 952, sala 02.
Palestrante: Pedro Arraes (Departamento de Matemática, UFC)
Título: Convexity in Oriented graphs
Resumo: Given an oriented graph $D=(V,A)$ and $u,v \in V(D)$, a $(u,v)$-geodesic is an oriented path in $D$, from $u$ to $v$, with smallest length. For a subset $S \subseteq V(D)$, the interval function $I:P(V(D)) \to P(V(D))$, where $P(V(D)) := \{ S \mid S \subseteq V(D) \}$, associates $S$ with $I[S] := \{ w \in V(D) \mid w$ is in a $(u,v)$-geodesic or in a $(v,u)$-geodesic of $D \}$. $S$ is said to be convex if $S=I[S]$. The convex hull of $S$, $[S]$, is the smallest convex subset of $V(D)$ that contains $S$, which is obtained by iterating the interval function until we obtain $I^n[S]=I^{n+1}[S]=[S]$. A hull set of $V(D)$ is a subset $S \subset V(D)$ such that $[S]=V(D)$. The hull number of $D$, $hn(D)$, is the cardinality of the smallest hull set of $D$.In this presentation, we will also show a few important results in the matter and some that we obtained in our studies.

Data/horário: 30/09/2016 – 13:00h.
Local: 952, sala de seminários.
Palestrante: Profa. Ana Shirley Silva (Departamento de Matemática, UFC)
Título: Grafos com cintura alta são b-contínuos
Slides
Resumo:Uma $b$-coloração dos vértices de uma grafo $G$ é uma coloração própria de $G$ onde cada classe de cor possui um vértice adjacente a cada outra classe de cor. O número $b$-cromático de $G$ é o maior inteiro $k$ para o qual existe uma $b$-coloração de $G$ com $k$ cores; este valor é denotado por $b(G)$. Nem sempre é válido que $G$ possui uma $b$-coloração com $k$ cores para todo inteiro no intervalo entre $\chi(G)$ e $b(G)$. Quando este é o caso, diz-se que $G$ é um grafo $b$-contínuo. Neste trabalho, provamos que todo grafo com cintura ao menos $10$ é $b$-contínuo, o que contribui para a intuição de que grafos com cintura alta são mais fáceis de $b$-colorir, além de generalizar em parte resultados anteriores da literatura. Este trabalho foi feito em co-autoria com a Profa. Cláudia Linhares Sales e foi apresentado no Cologne-Twente Workshop 2016.

Data/horário: 16/09/2016 – 16:00h.
Local: Bloco 952, sala 2.
Palestrante: Prof. Dr. Ignasi Sau (CNRS, LIRMM, Montpellier, France) (Departamento de Matemática, UFC)
Título: The number of labeled graphs of bounded treewidth
Slides
Resumo: Treewidth is one of the most fundamental parameters in modern graph theory and algorithms. Its theoretical importance is demonstrated by its crucial role in the proof of the Graph Minor theorem by Roberston and Seymour, while its algorithmic relevance is certified, for instance, by Courcelle’s theorem. In this talk we focus on couting the number of labeled graphs on $n$ vertices and treewidth $k$, which we denote by $T_{n,k}$. So far, only the particular cases $T_{n,1}$ and $T_{n,2}$ had been studied. Using a construction that exploits the fact that a graph has treewidth at most $k$ if and only if it is a partial $k$-tree, we show that$(c \cdot \frac{k}{\log k} \cdot 2^k \cdot n)^n \cdot 2^{-k(k+1)/2} \cdot k^{-2k-2}\ \leq\ T_{n,k}\ \leq\ \left(k \cdot 2^k \cdot n\right)^n \cdot 2^{-k(k+1)/2} \cdot k^{-k}$.Joint work with Julien Baste and Marc Noy, available atarXiv:1604.07273.

Data/horário: 20/05/2016 – 16:00h.
Local: Bloco 952, sala 2.
Palestrante: Raul Wayne (aluno mestrado, MDCC, UFC)
Título: Uma prova da conjectura de Gorgol
Resumo: O número de Turán $ex(n, F)$ é o máximo número de arestas que um grafo $G$ pode ter sem conter uma cópia de $F$ como subgrafo. Seja $P_3$ o grafo formado por um caminho de $3$ vértices e $kF$ o grafo formado pela união disjunta de $k$ cópias de um grafo $F$. Sendo $F$ um grafo conexo, Gorgol, em 2011, forneceu limites inferiores para $ex(n, kF)$ e conjecturou que o limite inferior oferecido era apertado quando $F = P_3$. Para $ex(n, kP_3)$, Gorgol mostrou, no mesmo artigo, que o limite inferior é de fato apertado quando $k=2$ ou $k=3$. Bushaw e Kettle mostraram que o limite também é apertado quando $n \geq 7k$. Ofereceremos uma prova construtiva para esta conjectura de Gorgol para quaisquer valores de $n$ e $k$. Em particular, oferecemos um algoritmo que, dado como entrada um grafo $G$ contendo mais arestas do que o limite inferior oferecido por Gorgol, retorna $k$ cópias disjuntas de $P_3$.

Data/horário: 13/05/2016 – 16:00h.
Local: A confirmar.
Palestrante: Prof. Rudini Sampaio (DC, UFC)
Título: Códigos de Identificação em Grides
Slides
Resumo: Seja $C$ um subconjunto de vértices de um grafo.
Dado um vértice $v$, o $C$-código de $v$ é o conjunto dos vértices de $N[v]$ que estão em $C$, onde $N[v]$ é a vizinhança fechada de $v$. Dizemos que $C$ é um código de identificação se todos os vértices tem $C$-código não-vazios distintos. O objetivo é encontrar um código de identificação com densidade mínima. Neste seminário, mostraremos resultados conhecidos em grides infinitos triangulares, retangulares, hexagonais e outros, bem como resultados novos em grides infinitos com número limitado de linhas.

Data/horário: 22/01/2016 – 16:00h.
Local: Bloco 914 (Dept Mat), sala 3.
Palestrante: Alexandre Azevedo Cezar (aluno doutorado, DMAT, UFC)
Título: Circular Backbone Colouring for Graphs of without Cycles of Size Four
Resumo:Dado um grafo $G$ e um subgrafo $H$ de $G$, uma $k$-coloração $q$-backbone de $(G,H)$ é uma função $c:V(G) \rightarrow \{1, …, k\}$ tal que, para toda aresta de $G$, os extremos da aresta possuem imagens diferentes e toda aresta de $H$ possuem imagens que diferem de no mínimo $q$. O número cromático $q$-backbone de $(G,H)$, denotado por $BBCq(G,H)$, é o menor inteiro $k$ tal que esta função $c$ existe. Similarmente, uma $k$-coloração $q$-backbone circular de $(G,H)$ é uma função $c:V(G) rightarrow \{1, …, k\}$ tal que, para toda aresta de $G$, os extremos da aresta possuem imagens diferentes e toda aresta de $H$ possuem imagens que diferem de no mínimo q e no máximo $k-q$. O número cromático $q$-backbone circular de $(G,H)$, denotado por $CBCq(G,H)$, é o menor inteiro $k$ tal que esta função $c$ existe. Nesta dissertação, primeiramente apresentamos um sumário dos resultados relacionados a Coloração Backbone. Após isto, mostramos que se $G$ é um grafo planar sem ciclos de tamanho quatro e $F$ é uma floresta geradora de caminhos induzidos de $G$, então $CBC2(G,H)$ é no máximo $7$. Este trabalho está intimamente relacionado com um demonstrado por Araújo et al. em um trabalho recente. Por fim, demonstramos o seguinte teorema que generaliza o trabalho de Bu et al.: se $G$ é conexo e $k$ é não muito pequeno, então existe uma $k$-coloração $q$-backbone de $(G,H)$, para algum subgrafo $H$ gerador conexo de $G$.

Universidade Federal do Ceará
ParGO – Paralelismo, Grafos e Otimização

Seminários 2016-2020

2020

2019

2018

2017

2016

Compartilhe: