IEEE Transactions on Multi-Scale Computing Systems

Expand your horizons with Colloquium, a monthly survey of abstracts from all CS transactions!


From the July-September 2018 issue

Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph

By Apurba Das and Srikanta Tirthapura

Featured article thumbnail image We consider incremental maintenance of maximal bicliques from a dynamic bipartite graph that changes over time due to the addition of edges. When new edges are added to the graph, we seek to enumerate the change in the set of maximal bicliques, without enumerating the set of maximal bicliques that remain unaffected. The challenge in an efficient algorithm is to enumerate the change without explicitly enumerating the set of all maximal bicliques. In this work, we present (1) Near-tight bounds on the magnitude of change in the set of maximal bicliques of a graph, due to a change in the edge set, and an (2) Incremental algorithm for enumerating the change in the set of maximal bicliques. For the case when a constant number of edges are added to the graph, our algorithm is “change-sensitive”, i.e., its time complexity is proportional to the magnitude of change in the set of maximal bicliques. To our knowledge, this is the first incremental algorithm for enumerating maximal bicliques in a dynamic graph, with a provable performance guarantee. Our algorithm is easy to implement, and experimental results show that its performance exceeds that of baseline implementations by orders of magnitude.

download PDF View the PDF of this article      csdl View this issue in the digital library


Editorials and Announcements

Announcements

  • The winner of the 2017 Best TMSCS Paper Award is:
    "Enabling New Computation Paradigms with HyperFET - An Emerging Device"
    by Wei-Yu Tsai, Xueqing Li, Matthew Jerry, Baihua Xie, Nikhil Shukla, Huichu Liu, Nandhini Chandramoorthy, Matthew Cotter, Arijit Raychowdhury, Donald M Chiarulli, Steven P Levitan, Suman Datta, John Sampson, Nagarajan Ranganathan, Vijaykrishnan Narayanan
    IEEE Transactions on Multi-Scale Computing Systems, Vol. 2, Iss. 1, pp. 30-48, 2016.
  • We're pleased to announce that Partha Pratim Pande, professor at Washington State University, has accepted the position of inaugural Editor-in-Chief.

Editorials


Guest Editorials


Call for Papers

General Call for Papers

View PDF.


Reviewers List


Annual Index


Access Recently Published TMSCS Articles

RSS Subscribe to the RSS feed of recently published TMSCS content

mail icon Sign up for e-mail notifications through IEEE Xplore Content Alerts

preprints icon View TMSCS preprints in the Computer Society Digital Library


TMSCS is financially cosponsored by:

IEEE Computer SocietyIEEE Communications SocietyIEEE Nanotechnology Council

 

TMSCS is technically cosponsored by:

IEEE Council on Electronic Design Automation