VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks
    Bokal, Drago, 1978- ; Brešar, Boštjan ; Jerebic, Janja
    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 ▫$L_1$▫-sphere in ▫${\mathbb N}^n$▫ are precisely the lexicographically minimal elements of this subset. We also present an application in designing optimal CDMA-based wireless sensor networks.
    Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 160, iss. 4-5, 2012, str. 460-470)
    Vrsta gradiva - članek, sestavni del
    Leto - 2012
    Jezik - angleški
    COBISS.SI-ID - 16191577

    Povezava(-e):

    http://dx.doi.org/10.1016/j.dam.2011.11.007
    Digitalna knjižnica Univerze v Mariboru – DKUM

vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 160, iss. 4-5, 2012, str. 460-470)
loading ...
loading ...
loading ...

Vnos na polico