1. A Modified Decomposition Algorithm for Maximum Weight Bipartite Matching and Its Experimental Evaluation
- Author
-
Shibsankar Das, Rahul Kadyan, D, S, Indian Institute of Technology Guwahati (IIT Guwahati), Lab-STICC_UBS_CACS_MOCS, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), and Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Factor-critical graph ,General Computer Science ,Matching (graph theory) ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Random instances of weighted bipartite graph ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,02 engineering and technology ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,01 natural sciences ,Simplex graph ,lcsh:QA75.5-76.95 ,Combinatorics ,weighted bipartite matching ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,0202 electrical engineering, electronic engineering, information engineering ,Blossom algorithm ,Mathematics ,Hopcroft–Karp algorithm ,Discrete mathematics ,Applied Mathematics ,Graph algorithm ,random instances of graphs ,experimental evaluation ,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO] ,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] ,Edge-transitive graph ,010201 computation theory & mathematics ,Bipartite graph ,020201 artificial intelligence & image processing ,Bound graph ,combinatorial optimization ,lcsh:Electronic computers. Computer science ,graph decomposition ,Algorithm ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Let G be an undirected bipartite graph with positive integer weights on the edges. We refine the existing decomposition theorem originally proposed by Kao et al., for computing maximum weight bipartite matching. We apply it to design an efficient version of the decomposition algorithm to compute the weight of a maximum weight bipartite matching of G in O(\sqrt{|V|}W'/k(|V|,W'/N))-time by employing an algorithm designed by Feder and Motwani as a subroutine, where |V| and N denote the number of nodes and the maximum edge weight of G, respectively and k(x,y)=log(x) /log(x^2/y). The parameter W' is smaller than the total edge weight W, essentially when the largest edge weight differs by more than one from the second-largest edge weight in the current working graph in any decomposition step of the algorithm. In best the case, W'=O(|E|) where |E| is the number of edges of G and in the worst case, W'=W, that is, |E| \leq W' \leq W. In addition, we talk about a scaling property of the algorithm and research a better bound of the parameter W'. Experimental evaluations of randomly generated data show that the proposed improvement is significant in general.
- Published
- 2020