Linear-time algorithm for generating c-isolated bicliques. Issue 8 (3rd August 2017)

• Record Type: Journal Article
• Authors: Alamgir, Zareen; Karim, Saira; Husnine, Syed
• Is Part Of: International journal of computer mathematics. Volume 94:Issue 8(2017)
• Page Start: 1574
• Page End: 1590
• Publication Date: 2017-08-03
• Subjects: Combinatorial algorithm -- enumeration algorithm -- biclique -- isolated biclique -- graph algorithms; 68R10 -- 68Q25 -- 90C35 -- 05C69; Computers -- Periodicals; Numerical analysis -- Periodicals; Automation -- Periodicals; 004.0151
• DOI: 10.1080/00207160.2016.1226498
• Languages: English
• ISSNs: 0020-7160

Abstract

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.