Naomi Nishimura

Naomi Nishimura is an Associate Professor at the Cheriton School of Computer Science, University of Waterloo. She holds a Ph.D. from University of Toronto (1991) and researches combinatorial reconfiguration, parameterized complexity, and graph algorithms.

Her work develops efficient algorithms for reconfiguration problems, including recent advances in parallel implementations for atom reconfiguration using GPUs. Nishimura's research establishes theoretical foundations for transforming combinatorial structures through step-by-step modifications while maintaining solution properties.

Recent publications survey parameterized complexity landscapes for reconfiguration problems and introduce novel algorithms like the assignment-rerouting-ordering technique. Her group analyzes computational boundaries for problems involving independent sets, dominating sets, and graph minors.