In this paper, we present a semi-automtic method for segmenting carotid arteries in contrast enhanced (CE)-CT angiography (CTA) scans. The segmentation algorithm extracts the lumen of carotid arteries between user specfied locations. Specifically, the algorithm first detects the centerline representations between the user placed seed points. This centerline extraction algorithm is based on a minimal path detection algorithm which operates on a {\em medialness} map. The lumen of corotid arteries is extracted by using the global optimal graph-cuts algorithm~\cite{boykov:01} using the centerlines as input. The radius information contained in the centerline representation is used to normalize the gradient based weights of the graph. It is shown that this algorithm can sucessfully segment the carotid arteries without including calcified and non-calcified plaques in the segmentation results.