voltarData: 29/08/2018
Título: Uma condição de suficiência para o problema da quase-bipartição em grafos de distância-hereditária
Palestrante: Rodolfo Alves de Oliveira, INFES/UFF
Data: 29 de agosto de 2018, 13 h.
Local: Sala 407, Bloco H, Campus Gragoatá, UFF.
Resumo: Muitos dos problemas de partição do conjunto de vértices de um grafo apresentam aplicações interessantes, tais como no problema de agrupamento e detecção de relações em redes sociais, biológicas ou de transporte, no processamento de imagens, no desenvolvimento de sistemas VLSI, no {\it pagerank} de páginas web e nos problemas de escalonamento de tarefas. Apresentaremos alguns aspectos teóricos sobre o problema de quase-bipartição na classe dos grafos de distância-hereditária. Considere um grafo $G =(V,E)$, uma quase-bipartição de $G$ é uma partição do conjunto de vértices $V$ em dois subconjuntos $\mathcal S$ e $\mathcal F$, onde $\mathcal S$ é um conjunto estável (ou independente) e $\mathcal F$ é um conjunto acíclico (isto é, induz um subgrafo acíclico). Veremos que o problema aplicado nos grafos de distância-hereditária possui um conjunto infinito de subgrafos proibidos dos quais não admitem uma quase-bipartição e mostraremos uma condição suficiente que garanta a existência da mesma para tal classe de grafos.
Obs. Trabalho em conjunto conjunto com os professores Raquel Bravo (IC/UFF) e Uéverton Souza (IC/UFF), e o aluno Fábio Silva Jr. (IC/UFF).
Confira aqui a apresentação