Bisimplicial edges in bipartite graphs

作者：Bomhoff Matthijs^*; Manthey Bodo

来源：Discrete Applied Mathematics, 2013, 161(12): 1699-1706.

DOI：10.1016/j.dam.2011.03.004

• Bipartite graphs
• Random graphs
• Algorithms
• Gaussian elimination

Bisimplicial edges in bipartite graphs are closely related to pivots in Gaussian elimination that avoid turning zeroes into non-zeroes. We present a new deterministic algorithm to find such edges in bipartite graphs. Our algorithm is very simple and easy to implement. Its running-time is O (nm), where n is the number of vertices and m is the number of edges. Furthermore, for any fixed p and random bipartite graphs in the G(n,n,p) model, the expected running-time of our algorithm is O (n(2)), which is linear in the input size.

• 出版日期2013-8