On the complexity of the (approximate) nearest colored node problem

Maximilian Probst

Given a graph $G=(V,E)$ where each vertex is assigned a color from the set $C=\{c_1,c_2,..,c_{\sigma }\}$. In the (approximate) nearest colored node problem, we want to query, given $v…