Range-Relaxed Graceful Game

Speaker: Deise L. de Oliveira, UFF.

Date: 26 aug 2020, 16h.

Place: Google Meet: meet.google.com/ces-qqwf-coo.

Abstract: The Range-Relaxed Graceful Game is played in a simple graph G, by two players, Alice and Bob, who alternately assign a previously unused label f(v) \in £={0, ..., k}, k >=|E(G)|, to a previously unlabeled vertex v \in V(G). Alice's goal is to end up with a vertex labeling of whole G where all of its edges have distinct labels and Bob's goal is to prevent it from happening. When k=|E(G)|, it is called Graceful game. We investigate the graceful game in cartesian and corona products of graphs, and determine that Bob has a winning strategy in all investigated families independently of who starts the game. Additionally, we present the first results in the range-relaxed graceful game.

Obs.: This joint work with Simone Dantas (IME-UFF) and Atílio G. Luiz (UFC), was accepted for presentation and publication in the CTW 2020 (18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization).

Support:

http://printbiotec.uff.br/ 

www.antenabrasil.uff.br

https://www.facebook.com/antenabrasileiradematematica/ 

 

 

Relating hypergraph parameters of generalized power graphs

Speaker: Lucas L. S. Portugal, IME-UFF.

Date: 29 jul 2020, 16h.

Place: Google Meet: https://meet.google.com/xwi-ijfn-mpc.

Abstract: Graph parameters like the chromatic number, independence number, clique number and many others alongside with their corresponding adjacency matrix have been broadly studied and extended to hypergraphs classes. A generalized power graph $G^k_s$ of a graph $G$ is $k$-uniform hypergraph constructed by blowing up each vertex of $G$ into a $s$-set of vertices and then adding $k-2s$ vertices of degree one to each edge, where $k\geq 2s$. A natural question is whether there exists any relation between structural parameters and spectral parameters of $G^k_s$ with the respective parameters of the original graph $G$. In this paper we positively answer this question and investigate the parameters behavior.

Obs.: This joint work with Renata Del Vecchio (IME/UFF) and Simone Dantas (IME/UFF), was accepted for presentation and publication in the CTW 2020 (18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization).

Support:

http://printbiotec.uff.br/ 

www.antenabrasil.uff.br

https://www.facebook.com/antenabrasileiradematematica/ 

 

 

Recent algorithmic results on equitable coloring

Speaker: Vinicius Santos, UFMG.

Date: 18 dec 2019, 11h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: A proper coloring of a graph is a labeling of its vertex set such that adjacent vertices receive distinct labels. Many problems can be modelled using graph colorings, such as scheduling and task assignment problems. On such problems, one may be interested in the case where the coloring is balanced in the following sense: the number of times two different colors occurs in the graph can differ by at most one. Such proper colorings are called equitable colorings.

Similarly to the traditional version, determining whether a graph has an equitable coloring with a given amount of colors is a computationally hard problem. However, for many settings where coloring is tractable, the problem becomes hard for the equitable version. In this talk we present some recent advances on this problem, such as polynomial time algorithms for some special cases and positive and negative results concerning the parameterized complexity of the problem.

This is joint work with Matheus Guedes and Guilherme Gomes.

 

Introdução sobre complexidade parametrizada e problemas

Speakers: Ignasi Sau, LIRMM; Ueverton Souza, IC-UFF.

Date: 27 nov 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: 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ão apresentados alguns problemas de nosso interesse particular tais como deleção de vértices em grafos com bounded treewidth para obtenção de estruturas livres de certos subgrafos induzidos. Em especial abordaremos o desenvolvimento de algoritmos de tempo single-exponencial com relação a treewidth do grafo de entrada para resolução problemas como deleção de vértices para obtenção de grafos livres de conjuntos independentes induzidos de tamanho k.

 

Jogo Mapa do Tesouro

Speaker: Andressa Martins Moraes, UFRJ/PPGI/AMN.

Date: 30 sep 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Neste seminário apresentarei o Jogo Mapa do Tesouro, um jogo em grafos aplicado na educação com objetivo de avaliar o desenvolvimento da aprendizagem utilizando conceitos da neurociência e empregando uma estrutura baseada em grafos.

 

Mais artigos...

Pagina 4 de 6