VLDB 2026 Research / reviewers in the wild / expert
Nicolas Almeida Martins
dblp:137/5079
· DBLP profile ↗
11ranked-venue papers
1as first author
8since 2021 · last 2026
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 11 · 1 first-author · 8 since 2021Databases, data management, data science and information retrieval · 1 · 1 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | The harmonious coloring game
Cláudia Linhares Sales, Thiago Braga Marcilon, Nicolas Almeida Martins, Nicolas Nisse, Rudini Menezes Sampaio |
Inf. Process. Lett. | 3 |
| 2026 | The Normal Domination Game in graphs
João Marcos Brito, Thiago Braga Marcilon, Nicolas Almeida Martins, Rudini Menezes Sampaio |
J. Comput. Syst. Sci. | 3 |
| 2025 | The Graph Coloring Game on 4 x n-GridsabstractThe graph coloring game is a famous two-player game (re)introduced by Bodlaender in 1991. Given a graph G and k ϵ N , Alice and Bob alternately (starting with Alice) color an uncolored vertex with some color in {1, • • •, k] such that no two adjacent vertices receive a same color. If eventually all vertices are colored, then Alice wins and Bob wins otherwise. The game chromatic number χ g (G) is the smallest integer k such that Alice has a winning strategy with k colors in G . It has been recently (2020) shown that, given a graph G and k ϵ N, deciding whether χ g (G) ≤ k is PSPACE-complete. Surprisingly, this parameter is not well understood even in “simple” graph classes. Let P n denote the path with n ≥ 1 vertices. For instance, in the case of Cartesian grids, it is easy to show that χ g ( P m □ P n ) ≤ 5 since χ g (G) ≤ ∆ + 1 for any graph G with maximum degree ∆. However, the exact value is only known for small values of m , namely χ g (P 1 □ P n ) = 3, χ g (P 2 □ P n ) = 4 and χ g ( P 3 □ Pn ) = 4 for n ≥ 4 [Raspaud, Wu, 2009]. Here, we prove that, for every n ≥ 18, χ g ( P 4 □ P n ) = 4. Caroline Brosse, Nicolas Almeida Martins, Nicolas Nisse, Rudini Menezes Sampaio |
LAGOS | 2 |
| 2025 | The Convex Set Forming Game
Caroline Brosse, Nicolas Almeida Martins, Nicolas Nisse, Rudini Menezes Sampaio |
Theor. Comput. Sci. | 2 |
| 2023 | The connected greedy coloring game
Carlos V. G. C. Lima, Thiago Braga Marcilon, Nicolas Almeida Martins, Rudini Menezes Sampaio |
Theor. Comput. Sci. | 3 |
| 2022 | Spy game: FPT-algorithm, hardness and graph products
Eurinardo Rodrigues Costa, Nicolas Almeida Martins, Rudini Menezes Sampaio |
Theor. Comput. Sci. | 2 |
| 2022 | PSPACE-hardness of variants of the graph coloring game
Carlos V. G. C. Lima, Thiago Braga Marcilon, Nicolas Almeida Martins, Rudini Menezes Sampaio |
Theor. Comput. Sci. | 3 |
| 2021 | Spy Game: FPT-Algorithm and Results on Graph Products
Eurinardo Rodrigues Costa, Nicolas Almeida Martins, Rudini Menezes Sampaio |
COCOON | 2 |
| 2020 | Hardness of Variants of the Graph Coloring Game
Thiago Braga Marcilon, Nicolas Almeida Martins, Rudini Menezes Sampaio |
LATIN | 2 |
| 2018 | Spy-game on graphs: Complexity and simple topologies
Nathann Cohen, Nicolas Almeida Martins, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes, Rudini Menezes Sampaio |
Theor. Comput. Sci. | 2 |
| 2018 | Locally identifying coloring of graphs with few P4s
Nicolas Almeida Martins, Rudini Menezes Sampaio |
Theor. Comput. Sci. | 1 |