A generalization of Hungarian method and Hall%26apos;s theorem with applications in wireless sensor networks

作者：Bokal Drago; Bresar Bostjan; Jerebic Janja^*

来源：Discrete Applied Mathematics, 2012, 160(4-5): 460-470.

DOI：10.1016/j.dam.2011.11.007

• Matching
• Quasi-matching
• Semi-matching
• Flow
• Hungarian method
• Augmenting path

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%26apos;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 L-1-sphere in N-n are precisely the lexicographically minimal elements of this subset. We also present an application in designing optimal COMA-based wireless sensor networks.

• 出版日期2012-3