COP-KMeans
Constrained Pairwise k-Means
COP-KMeans is a modified version the popular k-means algorithm that supports pairwise constraints. 

Original paper : Constrained K-means Clustering with Background Knowledge, Wagstaff et al. 2001