Automated anatomical labeling of the arteries forming the Circle of Willis is of great interest as facilitates inter-subject comparison required to discover geometric risk factors for the development of vascular pathologies. In this paper, we present a method for anatomical labeling of vessels forming anterior part of the Circle of Willis by detecting the five main vessel bifurcations. The method is first trained on a set of pre-labeled examples, where it learns local bifurcation features as well as global variation in the anatomy of the extracted vascular trees. Then the labeling of the target vascular tree is formulated as maximum a posteriori solution where the classifications of individual bifurcations are regularized by the prior learned knowledge of the tree they span. The method was evaluated by cross-validation on 30 subjects, which showed the vascular trees were correctly anatomically labeled in 90% of cases. The proposed method can naturally handle anatomical variations and is shown to be suitable for labeling arterial segments of Circle of Willis.