A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks TeX Export

@article{citeulike:6087195, abstract = {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 vast 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 also present an application in designing an optimal CDMA-based wireless sensor networks.}, archivePrefix = {arXiv}, author = {Bokal, D. and Bresar, B. and Jerebic, J.}, citeulike-article-id = {6087195}, citeulike-linkout-0 = {http://arxiv.org/abs/0911.1269}, citeulike-linkout-1 = {http://arxiv.org/pdf/0911.1269}, day = {6}, eprint = {0911.1269}, keywords = {assignment}, month = {Nov}, posted-at = {2009-11-09 07:09:24}, priority = {2}, title = {A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks}, url = {http://arxiv.org/abs/0911.1269}, year = {2009} }

TY - JOUR ID - citeulike:6087195 L3 - citeulike-article-id:6087195 N2 - 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 vast 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 also present an application in designing an optimal CDMA-based wireless sensor networks. TI - A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks KW - assignment AU - Bokal, D AU - Bresar, B AU - Jerebic, J PY - 2009/Nov/06/ UR - http://arxiv.org/abs/0911.1269 ER -