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

DOI10.1016/J.DAM.2011.11.007zbMATH Open1237.05159arXiv0911.1269OpenAlexW2090605216MaRDI QIDQ412342FDOQ412342

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

Publication date: 4 May 2012

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

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.

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)

Cites Work

• On Representatives of Subsets
• Semi-matchings for bipartite graphs and load balancing
• On-line load balancing
• Faster Algorithms for Semi-matching Problems (Extended Abstract)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

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

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)