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

DOI10.1016/J.DAM.2011.11.007zbMath1237.05159arXiv0911.1269OpenAlexW2090605216MaRDI QIDQ412342

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

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

Related Items (10)

An extension of Hall's theorem for partitioned bipartite graphs ⋮ On computing an optimal semi-matching ⋮ Solving the at-most-once problem with nearly optimal effectiveness ⋮ Deadlock resolution in wait-for graphs by vertex/arc deletion ⋮ Distributed backup placement in networks ⋮ Faster Algorithms for Semi-Matching Problems ⋮ 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 ⋮ Decreasing minimization on M-convex sets: algorithms and applications

Cites Work

• On-line load balancing
• Faster Algorithms for Semi-matching Problems (Extended Abstract)
• On Representatives of Subsets
• Semi-matchings for bipartite graphs and load balancing
• Unnamed Item
• Unnamed Item

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