All Questions

I've been running into this problem recently and I've been stuck on it for a while. I have a set of vertices $G$ that form a complete graph. From this I need to sample $k$ vertices (which would also ...

I need to compute the minimum euclidean spanning tree in $R^d$ and do it with some algorithm that can do it with complexity near to $\Omega(nlogn)$ where $n$ is the size of the point set. Right now I'...

Given an $n \times n$ grid with unit grid cells, and one point from the interior of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound ...