Technical Report CS-2011-04

TR#:CS-2011-04
Class:CS
Title: Algorithms for maximum induced multicliques and complete multipartite subgraphs in polygon-circle graphs
Authors: Fanica Gavril
PDFCS-2011-04.pdf
Abstract: 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. The complement of a graph G is denoted coG. 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 polynomial time algorithms to find in polygon-circle graphs induced maximum and maximum balanced: multicliques and complete multipartite subgraphs. We describe polynomial time algorithms to find in circle graphs induced maximum and maximum balanced multiclique-multipartite subgraphs. 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2011/CS/CS-2011-04), rather than to the URL of the PDF or PS 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