کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872600 | 684166 | 2012 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks](/preview/png/6872600.png)
چکیده انگلیسی
In this paper, we consider various problems concerning quasi-matchings and semi-matchings in bipartite graphs, which generalize the classical problem of determining a perfect matching in bipartite graphs. We prove a generalization of Hall's marriage theorem, and present an algorithm that solves the problem of determining a lexicographically minimum g-quasi-matching (that is a set F of edges in a bipartite graph such that in one set of the bipartition every vertex v has at least g(v) incident edges from F, where g is a so-called need mapping, while on the other side of the bipartition the distribution of degrees with respect to F is lexicographically minimum). We obtain that finding a lexicographically minimum quasi-matching is equivalent to minimizing any strictly convex function on the degrees of the A-side of a quasi-matching and use this fact to prove a more general statement: the optima of any component-based strictly convex cost function on any subset of L1-sphere in Nn are precisely the lexicographically minimal elements of this subset. We also present an application in designing optimal CDMA-based wireless sensor networks.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issues 4â5, March 2012, Pages 460-470
Journal: Discrete Applied Mathematics - Volume 160, Issues 4â5, March 2012, Pages 460-470
نویسندگان
Drago Bokal, Boštjan Brešar, Janja Jerebic,