TR#: | CS-2011-04 |

Class: | CS |

Title: | Algorithms for maximum induced multicliques and complete multipartite subgraphs in polygon-circle graphs |

Authors: | Fanica Gavril |

CS-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 uU, vW 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. |

Copyright | The 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 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