Research
Theses and papers
String algorithms, graph partitions, and data structures for sets and arrays.
Papers
String Matching with a Dynamic Pattern. Bruno Monteiro, Vinicius dos Santos. SPIRE 2025.
String matching when the pattern is edited: insert and delete characters, then count occurrences in a static text. Using suffix arrays we get O(log |T|) updates after O(|T|) preprocess, and the same bounds for substring delete, transpose, and copy, plus an online text.
Equitable Partition of Graphs into Independent Sets and Cliques. Bruno Monteiro, Vinicius dos Santos. ETC 2019.
A graph is (k, ℓ) if its vertices can be partitioned into k independent sets and ℓ cliques. Deciding an equitable such partition is polynomial when max(k, ℓ) ≤ 2, and NP-complete otherwise.
Master's thesis
String Matching with a Dynamic Pattern. Bruno Maletta Monteiro. Master's thesis, UFMG, 2024. Advisor Vinicius Fernandes dos Santos. Committee: Victor Campos, Felipe Alves da Louza.
The dissertation the SPIRE paper is based on.
Bachelor's thesis
Efficient Operations on Dynamic Arrays / Operações Eficientes em Arrays Dinâmicos. Bruno Monteiro. Bachelor's thesis, UFMG, 2021. Advisor Vinicius dos Santos.
Integer-set representation with merge and split in O(log U) amortized. A Block-Sorted Array supporting split, concat, reverse, and sort in O(log n + log U), plus a Partition operation that removes the k smallest values (conjectured sublinear).
PDF · code · related tutorial