Answers are grounded in this paper and cite their sources.
Given a set of edge pairs in a complete bipartite graph, the objective of the maximum edge-pair embedding bipartite b-matching problem (MEEBbM) is to find a bipartite b-matching that includes the maximum number of these edge pairs. The original problem, known as the maximum edge-pair embedding bipartite matching, was demonstrated to be NP-hard and inapproximable by Nguyen et al. in 2021. Building on this, and being inspired by the optimization of reconfigurable networks, we extend the problem in this paper to consider b-matchings, with a focus on scenarios where the number of edge pairs per node is bounded. Let k k represent the maximum number of edge pairs that can be incident on a single node. We prove that when $$k > b$$ k > b , the problem is NP-hard. For the case when $$b = 2$$ b = 2 , we provide an exact algorithm for $$k = 1,2$$ k = 1 , 2 . Additionally, for any values of k and b, we provide a Θ (k) Θ ( k ) -approximation algorithm for this problem.
No takes yet. Share an insight, caveat, or question.
Buahong et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: