Technical Report CS-2011-11

Title: Maximum induced multicliques and complete multipartite subgraphs in polygon-circle graphs and circle graphs
Authors: Fanica Gavril
Abstract: This is a Revised Version of CS-2011-04. A graph is a multiclique if its connected components are cliques. A graph is a complete multipartite graph if its vertex set has a partition into independent sets such that every two vertices in different independent sets are adjacent. A graph is a multiclique-multipartite graph if its vertex set has a partition U, W such that G(U) is complete multipartite, G(W) is a multiclique and every two vertices uU, vW are adjacent. We describe a polynomial time algorithm to find maximum induced complete multipartite subgraphs in polygon-circle graphs. We describe polynomial time algorithms to find maximum induced multicliques and multiclique-multipartite subgraphs in circle graphs. These problems have applications for clustering of proteins by PPI criteria, of documents, and of web pages.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2011
To the main CS technical reports page

Computer science department, Technion