5 papers
The Monophonic Directed Convexities
Júlio Araújo, Ana Karolinna Maia, Thiago Marcilon +2
Graph Convexity is a topic with many papers in the literature, especially on the , geodesic, and monophonic convexities in undirected graphs. Regarding directed graphs, Erd{\H…
The complexity of convexity number and percolation time in the cycle convexity
Carlos V. G. C. Lima, Thiago Marcilon, Pedro Paulo de Medeiros
The subject of graph convexity is well explored in the literature, the so-called interval convexities above all. In this work, we explore the cycle convexity, an interval convexity…
Hardness of some variants of the graph coloring game
Thiago Marcilon, Nicolas Martins, Rudini Sampaio
Very recently, a long-standing open question proposed by Bodlaender in 1991 was answered: the graph coloring game is PSPACE-complete. In 2019, Andres and Lock proposed five variant…
The maximum time of 2-neighbor bootstrap percolation: complexity results
Thiago Braga Marcilon, Rudini Menezes Sampaio
In 2-neighborhood bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: infected vertices of G remain infected forever and in cons…
The maximum time of 2-neighbour bootstrap percolation in grid graphs and some parameterized results
Thiago Braga Marcilon, Rudini Menezes Sampaio
In 2-neighborhood bootstrap percolation on a graph , an infection spreads according to the following deterministic rule: infected vertices of remain infected forever and in…