Graph Clustering: Complexity, Sequential and Parallel Algorithms

• Author(s) / Creator(s)

  • Abbas, Nesrine

• Technical report TR95-01. In this thesis we study graph clustering on two well known families of graphs that arise in many applications, namely bipartite and chordal graphs. We study two specific types of clustering problems. On the one hand we seek a partition of the vertex set of a graph into a bounded number of sets so that a prespecified function determined by the diameters of the induced sub-graphs is minimized. On the other hand we seek one subset of the vertex set that has a fixed number of vertices and induces the maximum possible number of edges. The first problem type constitutes the main theme of this thesis. We define a class of functions on partitions of vertices, which we call monotone diameter functions, that will enable us to group many problems into one general problem. Examples of these problems are the following: partition the vertices of a graph into a limited number of sub-graphs of bounded diameter, and partition the vertices of a graph into a limited number of subgraphs so that the sum of the diameters of the subgraphs is bounded. We prove that the problem of partitioning the vertices of a graph into subgraphs of bounded diameter is NP-complete on bipartite and chordal graphs. In contrast with these negative results, we give linear time sequential algorithms for the same problem on bipartite permutation and interval graphs, the first being a subset of bipartite graphs and the second being a subset of chordal graphs. We also present efficient parallel algorithms for the general problem on biconvex and interval graphs. During the course of studying this problem on biconvex graphs, we prove that biconvex graphs have a certain ordering of the vertices, which we call a biconvex straight ordering, that has promising algorithmic potential. We present an efficient parallel algorithm for constructing a biconvex straight ordering for any biconvex graph. We also study the problem of finding a cluster of bounded size with the maximum possible number of edges, and present an efficient parallel algorithm for solving this problem on a class of unit interval graphs. | TRID-ID TR95-01

• Date created

  1995

• Subjects / Keywords

  • Graph clustering
  • Parallel algorithms

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R32F7JR3J

• License

  Attribution 3.0 International