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

DOI10.1016/J.DAM.2011.11.007MaRDI QIDQ412342zbMATH OpenOpenAlexFDO

Authors Janja Jerebic, Drago Bokal, Boštjan Brešar

Publication date 4 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.1269

zbMATH Keywords

matchingflowaugmenting pathHungarian methodquasi-matchingsemi-matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Network design and communication in computer systems (68M10)

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.

Recommendations

• scientific article; zbMATH DE number 795216
• Semi-matchings for bipartite graphs and load balancing
• On computing an optimal semi-matching
• scientific article; zbMATH DE number 1003236
• Constrained matching problems in bipartite graphs

Cites work

• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• Faster algorithms for semi-matching problems (extended abstract)
• Graph theory
• On Representatives of Subsets
• On-line load balancing
• Semi-matchings for bipartite graphs and load balancing

Cited in

(10)

• Solving the at-most-once problem with nearly optimal effectiveness
• Decreasing minimization on M-convex sets: background and structures
• On computing an optimal semi-matching
• Distributed backup placement in networks
• Decreasing minimization on M-convex sets: algorithms and applications
• An extension of Hall's theorem for partitioned bipartite graphs
• Deadlock resolution in wait-for graphs by vertex/arc deletion
• Faster algorithms for semi-matching problems
• On computing an optimal semi-matching
• The existence of universally agreed fairest semi-matchings in any given bipartite graph

This page was built for publication: A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412342)