20.500.12556/DKUM-51803 A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks 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. matematika teorija grafov prirejanje kvazi prirejanje polprirejanje tok madžarska metoda mathematics graph theory matching quasi-matching semi-matching flow Hungarian method augmenting path true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 15:11:00 2015-07-10 15:11:00 2022-05-30 03:07:27 2019-07-11 07:28:43 2009 0 0 str. 1-15 št. 1102 Vol. 47 2009 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1318-4865 519.17:004 44310272 15306329 URN:SI:UM:DK:WZIKEP5L http://www.imfm.si/preprinti/PDF/01102.pdf 1 https://dk.um.si/Dokument.php?lang=slv&id=76363 Fakulteta za naravoslovje in matematiko 0 0 0