کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420000 | 683882 | 2013 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bisimplicial edges in bipartite graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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)O(nm), where nn is the number of vertices and mm is the number of edges. Furthermore, for any fixed pp and random bipartite graphs in the Gn,n,pGn,n,p model, the expected running-time of our algorithm is O(n2)O(n2), which is linear in the input size.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issue 12, August 2013, Pages 1699–1706
Journal: Discrete Applied Mathematics - Volume 161, Issue 12, August 2013, Pages 1699–1706
نویسندگان
Matthijs Bomhoff, Bodo Manthey,