2017/07/25 by Apurba Das, Srikanta Tirthapura, Das, Apurba +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #Formal Methods in Verification #Gene Regulatory Network Analysis #Microbial Metabolic Engineering and Bioproduction
paper · pdf · doi:10.48550/arxiv.1707.08272
openalex publication_date 2017/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the maintenance of maximal bicliques from a dynamic bipartite\ngraph that changes over time due to the addition or deletion of edges. When the\nset of edges in a graph changes, we are interested in knowing the change in the\nset of maximal bicliques (the "change"), rather than in knowing the set of\nmaximal bicliques that remain unaffected. The challenge in an efficient\nalgorithm is to enumerate the change without explicitly enumerating the set of\nall maximal bicliques. In this work, we present (1) near-tight bounds on the\nmagnitude of change in the set of maximal bicliques of a graph, due to a change\nin the edge set (2) a "change-sensitive" algorithm for enumerating the change\nin the set of maximal bicliques, whose time complexity is proportional to the\nmagnitude of change that actually occurred in the set of maximal bicliques in\nthe graph. To our knowledge, these are the first algorithms for enumerating\nmaximal bicliques in a dynamic graph, with such provable performance\nguarantees. Our algorithms are easy to implement, and experimental results show\nthat their performance exceeds that of current baseline implementations by\norders of magnitude.\n