Linear-time algorithm for generating c-isolated bicliques

ABSTRACT

Bicliques are widely used to solve various real-world problems encountered in bio-informatics, data mining and networks. We consider c-isolated bicliques, a variation of bicliques. The c-isolated bicliques can model communities in social and biological networks. We propose an efficient algorithm to generate all c-isolated maximal bicliques in a given bipartite graph. Our algorithm exploits underlying properties of an isolated biclique to trim the input graph. Furthermore, the algorithm deploys the vertex cover enumeration algorithm based on fixed parameter tractability and lists all maximal c-isolated bicliques in linear time (in terms of graph size), for constant c.

KEYWORDS:

• Combinatorial algorithm
• enumeration algorithm
• biclique
• isolated biclique
• graph algorithms

2010 AMS SUBJECT CLASSIFICATIONS:

• 68R10
• 68Q25
• 90C35
• 05C69

Acknowledgments

We would like to thank anonymous referees for their valuable suggestions.

Disclosure statement

No potential conflict of interest was reported by the authors.