No preview available



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Computing Science, Department of


This file is in the following collections:

Technical Reports (Computing Science)

Graph Clustering: Complexity, Sequential and Parallel Algorithms Open Access


Author or creator
Abbas, Nesrine
Additional contributors
graph clustering
parallel algorithms
Type of item
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.
Date created
License information
Creative Commons Attribution 3.0 Unported

Citation for previous publication

Link to related item

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: postscript (Postscript)
Mime type: application/postscript
File size: 1427956
Last modified: 2015:10:12 12:48:23-06:00
Original checksum: 6228e10430208c94059f09651ad26ab9
Activity of users you follow
User Activity Date