@inproceedings{1d0c45778bea410c8fad8f4f9d3ed0d0,

title = "Bisimplicial edges in bipartite graphs",

abstract = "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 nd such edges in bipartite graphs. The expected time complexity of our new algorithm is $O(n^2 \log n)$ on random bipartite graphs in which each edge is present with a fixed probability p, a polynomial improvement over the fastest algorithm found in the existing literature.",

keywords = "IR-75056, METIS-275736, Gaussian elimination, Probabilistic Analysis, Random matrices, EWI-18961, Bisimplicial edges",

author = "M.J. Bomhoff and Bodo Manthey",

year = "2010",

language = "Undefined",

isbn = "not assigned",

publisher = "University of Cologne",

pages = "29--32",

editor = "U. Faigle and R. Schrader and D. Herrmann",

booktitle = "Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010)",

note = "null ; Conference date: 25-05-2010 Through 27-05-2010",

}