A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networksBokal, Drago (Avtor) Brešar, Boštjan (Avtor) Jerebic, Janja (Avtor) matematikateorija grafovprirejanjekvazi prirejanjepolprirejanjetokmadžarska metodamathematicsgraph theorymatchingquasi-matchingsemi-matchingflowHungarian methodaugmenting pathIn 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.20092015-07-10 15:11:00Delo ni kategorizirano51803ISSN: 1318-4865UDK: 519.17:004OceCobissID: 44310272COBISS_ID: 15306329NUK URN: URN:SI:UM:DK:WZIKEP5Lsl