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

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

2009-11-06

arxiv.org/abs/0911.1269v1

Mathematics

Combinatorics

15 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-391339