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
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.
Editorials and 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.
- Editorial (April-June 2017)
- Editorial (Jan-March 2016)
- Introduction to IEEE Transactions on Multiscale Computing Systems (TMSCS) (Jan-March 2015)
- Welcome Message (Jan-March 2015)
- Guest Editorial: Advances in Parallel Graph Processing: Algorithms, Architectures, and Application Frameworks (July-September 2018)
- Guest Editorial: Emerging Technologies and Architectures for Manycore Computing Part 1: Hardware Techniques (April-June 2018)
- Guest Editorial: Special Issue on Accelerated Computing (January-March 2018)
- Design and Applications of Neuromorphic Computing System (Oct-Dec 2016)
- Hardware/Software Cross-Layer Technologies for Trustworthy and Secure Computing (July-Sept 2016)
- Emerging Memory Technologies—Modeling, Design, and Applications for Multi-Scale Computing (July-Sept 2015)
- Wearables, Implants, and Internet of Things (April-June 2015)
Call for Papers
General Call for Papers
Access Recently Published TMSCS Articles
Subscribe to the RSS feed of recently published TMSCS content
Sign up for e-mail notifications through IEEE Xplore Content Alerts
View TMSCS preprints in the Computer Society Digital Library
TMSCS is financially cosponsored by:
TMSCS is technically cosponsored by: