Finding short vectors in a lattice of Voronoi's first kind

Robby McKilliam, Alex Grant

We show that for those lattices of Voronoi's first kind, a vector of shortest nonzero Euclidean length can computed in polynomial time by computing a minimum cut in a graph.