We present a novel algorithm for the simultaneous segmentation and anatomical labeling of the cerebral vasculature. Unlike existing approaches that first attempt to obtain a good segmentation and then perform labeling, we optimize for both by simultaneously taking into account the image evidence and the prior knowledge about the geometry and connectivity of the vasculature. This is achieved by first constructing an overcomplete graph capturing the vasculature, and then selecting and labeling the subset of edges that most likely represents the true vasculature. We formulate the latter problem as an Integer Program (IP), which can be solved efficiently to provable optimality. We evaluate our approach on a publicly available dataset of 50 cerebral MRA images, and demonstrate that it compares favorably against state-of-the-art methods. (C) 2016 Elsevier B.V. All rights reserved.