Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms

We study a group of clustering problems on bipartite and chordal graphs. Ou r objective is to partition the vertices of a graph into a restricted numbe r of sets so that a prespecified, diameter related, objective function is m inimized. We unify a few problems using monotone diameter functions defined on sub-partitions of a graph. Among these problems are the following: part ition vertices of a graph into a restricted number of subgraphs of bounded diameter, and partition vertices of a graph into a restricted number of sub graphs so the sum of the diameters of the subgraphs is bounded. We show that the first of the aforementioned problems is NP-complete on bip artite and chordal graphs, but has linear time sequential solutions on inte rval and bipartite permutation graphs. As well, we show that the unified pr oblem has an NC parallel algorithm on interval graphs. (C) 1999 Published b y Elsevier Science B.V. All rights reserved.