Maximum cut and Steiner tree restricted to interval graphs and related families

Speaker: Celina de Figueiredo, COPPE UFRJ.

Date: 12 mai 2021, 14h.

Place: Google Meet: meet.google.com/nhe-vccv-qrf

Abstract: We consider Column 16 -- Graph Restrictions and Their Effect -- of D. S. Johnson's Ongoing guide, where several puzzles were proposed in a summary table with 30 graph classes as rows and 11 problems as columns, and several of the 330 entries remain unclassified into Polynomial or NP-complete after 35 years. We focus on columns MaxCut and StTree, where there are recent resolved entries for interval graphs and related families.

 

Colorações restritas de grafos aleatórios

Speakers: Guilherme Mota, USP.

Date: 28 apr 2021, 14h.

Place: Google Meet: meet.google.com/dra-gigp-gny.

Abstract: Dados grafos G, H_1 e H_2, denote por G ---> (H_1, H_2) a seguinte propriedade: em toda coloração das arestas de G há uma cópia monocromática de H_1 ou uma cópia "arco-íris" de H_2 (uma cópia de H_2 em que todas as arestas têm cores diferentes).

O número de Ramsey restrito, definido como o menor n tal que K_n ---> (H_1, H_2), existe se e somente se H_1 é uma estrela ou H_2 é uma floresta. Neste seminário vou determinar o "threshold" para a propriedade G (n, p) ---> (H_1, H_2) quando H_2 é uma floresta.

Este é um trabalho conjunto com Maurício Collares, Yoshiharu Kohayakawa e Carlos Gustavo Moreira.

 

Grupo de Thompson da Basílica

Speakers: Miguel Del Rio (doutor UNICAMP, 2019).

Date: 24 mar 2021, 16h.

Place: Google Meet: meet.google.com/dra-gigp-gny.

Abstract: O grupo de Thompson da Basílica, um grupo introduzido por Belk e Forrest em [2] e que tem relação com os grupos de Thompson F, T, V e muitos outros grupos com definições análogas a estes.

Nós estudaremos o problema da conjugação no grupo de Thompson da Basílica. Para isso vamos examinar a solução desse problema no grupo de Thompson T. Nossa solução usa uma técnica similar a aquela usada por Belk e Matucci em [3] com a vantagem de que achamos que pode ser usada em outros grupos como os grupos de rearranjos estudados por Belk e Forrest em [2].

[1] J. Belk and B. Forrest. A Thompson Group for the Basilica. Groups, Geometry, and Dynamics 9.4 (2015): 975–1000. doi:10.4171/GGD/333.

[2] J. Belk and B. Forrest. Rearrangement Groups of Fractals. Preprint (2015). arXiv:1510.03133.

[3] J. Belk and F. Matucci. Conjugacy and Dynamics in Thompson's Groups. Geometriae Dedicata 169.1 (2014): 239–261.

 

Propagação da COVID-19 usando medidas de centralidade de grafos

Speaker: Átila Arueira Jones, Inst. Federal do Sudeste de Minas Gerais.

Date: 02 dec 2020, 16h.

Place: Google Meet: meet.google.com/gbn-pvqf-bpw.

Abstract: Atualmente há uma grande preocupação na disseminação do vírus causador da doença COVID-19 e o distanciamento social ainda é a forma mais indicada para conter a propagação da doença. Neste trabalho modelamos a relação de alunos e professores de uma instituição de ensino através de um grafo para então simular a difusão do vírus, segundo o modelo epidêmico SIR. A propagação da epidemia foi observada tomando diferentes situações iniciais, a partir de um único vértice infectado inicial, de acordo com medidas de centralidade calculadas. Então observamos a influência dessas medidas na difusão do vírus e como isso está relacionado ao tempo do pico da epidemia.

Obs.: Trabalho em conjunto com Priscila R. Almeida (professora IFsudMG) e Luísa Gonçalves (graduando Engenharia Mecatrônica - IFsudMG).

 

On Undirected Two-commodity Integral Flow, Disjoint Paths and Strict Terminal Connection Problems

Speaker: Alexsander A. de Melo, COPPE-UFRJ.

Date: 30 sep 2020, 16h.

Place: Google Meet: meet.google.com/ost-kzem-mqk.

Abstract: Even, Itai and Shamir (1976) proved simple two-commodity integral flow is NP-complete both in the directed and undirected cases. In particular, the directed case was shown to be NP-complete even if one demand is unitary, which was improved by Fortune, Hopcroft and Wyllie (1980) who proved the problem is still NP-complete if both demands are unitary. The undirected case, on the other hand, was proved by Robertson and Seymour (1995) to be polynomial-time solvable if both demands are constant. Nevertheless, the complexity of the undirected case with exactly one constant demand has remained unknown. We close this forty year complexity gap, by showing the undirected case is NP-complete even if exactly one demand is unitary. As a by-product, we obtain the NP-completeness of determining whether a graph contains 1 + d pairwise vertex-disjoint paths, such that one path is between a given pair of vertices and d paths are between a second given pair of vertices. Additionally, we investigate the complexity of another related network design problem called Strict Terminal Connection.

Obs.: This is a joint work with Celina M. H. de Figueiredo (PESC/COPPE/UFRJ) and Uéverton dos Santos Souza (IC/UFF).

 

The monochromatic transversal game on clique-hypergraphs of powers of cycles

Speaker: Wilder P. Mendes, UFF.

Date: 26 aug 2020, 16h30.

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

Abstract: We introduce the monochromatic transversal game where the players, Alice and Bob, alternately colours vertices of a hypergraph. Alice, who colours the vertices with red, wins the game if she obtains a red transversal; and Bob wins if he does not let it happen, i.e. there exists a monochromatic blue hyperedge. Both players are enabled to start the game and they play optimally. We analyze the game played on clique-hypergraphs of complete graphs, paths, and powers of cycles. For each of these graphs, we show a strategy that allows one of the players to win the game.

Obs.: This joint work with Simone Dantas (IME/UFF), Sylvain Gravier (CNRS, Université Grenoble Alpes) and Rodrigo Marinho (IST, University of Lisbon, Portugal), 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/ 

 

 

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.

 

More Articles...

Page 2 of 3