-
Notifications
You must be signed in to change notification settings - Fork 0
/
report.tex
122 lines (93 loc) · 9.3 KB
/
report.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
\documentclass[oneside]{book}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{geometry}
\usepackage{mathtools}
\usepackage{listings}
\usepackage{hyperref}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage{float}
\usepackage{import}
\geometry{margin=1in}
\begin{document}
\begin{titlepage}
\centering
\scshape
\vspace*{12\baselineskip}
\rule{\textwidth}{1.6pt}\vspace*{-\baselineskip}\vspace*{2pt}
\rule{\textwidth}{0.4pt}
\vspace{0.75\baselineskip}
{\Large CS 406 : Algorithmic Graph Theory}{ \\\vspace{0.75\baselineskip} \LARGE Maximum Matching in Bipartite and General Graphs}
\vspace{0.75\baselineskip}
\rule{\textwidth}{0.4pt}\vspace*{-\baselineskip}\vspace{3.2pt}
\rule{\textwidth}{1.6pt}
\vspace*{3\baselineskip}
{\scshape\Large Bhargey Mehta\\ 201701074}
\vspace{3\baselineskip} %originally 0.5
\vspace{1\baselineskip}
\textit{\large Dhirubhai Ambani Institute of Information and Communication Technology \\ Gandhinagar\\}
\end{titlepage}
\chapter{Introduction \& Motivation}
\section{Blossom Algorithm}
The blossom algorithm was developed by Jack Edmonds in 1965. It works on general unweighted graphs. The algorithm is named blossom because the odd length cycles are called blossoms.
The algorithm finds an application in the development of chemistry development kit. In organic chemistry a lot of focus is present on how bonds interact with each other since 2 compounds having the same molecular formula but different bond structure behave differently. While doing computational chemistry one often needs to assign the double bonds to specific places so that the valency of the carbon atoms is satisfied.
This can be posed as a problem in graph theory such that each carbon atom is a vertex and each single bond is an edge. Now we need to assign double bonds to certain singly bonded atoms. These double bonds cannot occur at a single vertex so a single vertex can belong to at maximum 1 double bond. This leads to the fact that the double bonds form a matching in the graph generated by a compound. This leads to a need to solve the maximum matching problem algorithmically in polynomial time.
\section{Hopcroft-Karp Algorithm}
The Hopcroft Karp Algorithm was developed by John Hopcroft and Richard Karp in 1973. It solves a specialised case of the assignment problem when the edge weights are equal i.e. we don't have a preference for any agent or job. This algorithm is of interest since it is faster than the Hungarian algorithm. Applications include matching organ donors to compatible patients, matching (same preference) job applicants to companies in a job fair etc.
\section{Hungarian Algorithm}
The Hungarian algorithm was developed by Harold Kuhn in 1955 and reviewed by James Munkres in 1957 to be polynomial time. Kuhn had developed this algorithm mainly on the basis of work done by Hungarian mathematicians Dénes Kőnig and Jenő Egerváry so he named the algorithm the "Hungarian" algorithm.
The algorithm works on a complete weighted bipartite graph. This is of interest because a well known combinatorial problem called the assignment problem can be posed as finding the maximum or minimum weighted matching in this bipartite setting. We are given a list of agents and a list of tasks. These lists of agents and tasks are nothing but the bipartitions of the graph. Each agent does the listed tasks for some cost which is the edge weight. We want to assign an agent to a single task so that the overall cost is maximum or minimum. This translates to finding a maximum weighted matching in the graph. Applications include assigning machines to factories, bidding and contract assignments etc.
\chapter{Blossom Algorithm}
\include{blossom}
\chapter{Hopcroft-Karp Algorithm}
\newpage
\include{hopcroft}
\chapter{Hungarian Algorithm}
\newpage
\include{hungarian}
\chapter{Related Algorithms}
\section{Unweighted Maximum Matching in Bipartite Graphs}
\begin{itemize}
\item \href{https://epubs.siam.org/doi/10.1137/0202019}{\textcolor{blue}{1973: J Hopcroft, R Karp; An $N^{\frac{5}{2}}$ Algorithm for Maximum Matchings in Bipartite Graphs}}
\item \href{https://www.sciencedirect.com/science/article/abs/pii/002001909190195N}{\textcolor{blue}{1991: H Alt, N Blum, K Mehlhorn, M Paul; Computing a maximum cardinality matching in a bipartite graph in time O($n^{1.5}m\log n$)}}
\item \href{https://www.sciencedirect.com/science/article/pii/S0022000085710653}{\textcolor{blue}{1995: T Feder, R Motwani; Clique Partitions, Graph Compression and Speeding-Up Algorithms}}
\end{itemize}
\section{Weighted Maximum Matching in Bipartite Graphs}
\begin{itemize}
\item \href{https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800020109}{\textcolor{blue}{1955: H Kuhn ; The Hungarian method for the assignment problem}}
\item \href{https://www.orsj.or.jp/~archive/pdf/e_mag/Vol.03_01_02_027.pdf}{\textcolor{blue}{1960: M Iri; A New Method for Solving Transportation-Network Problems}}
\item \textcolor{blue}{1969: E Dinic, M Konrod; An Algorithm for the Solution of the Assignment Problem}
\item \href{https://www.sciencedirect.com/science/article/pii/002200008590039X}{\textcolor{blue}{1985: H Gabow; Scaling algorithms for network problems}}
\item \href{https://dl.acm.org/doi/10.1145/28869.28874}{\textcolor{blue}{1987: M Fredman, R Tarjan; Fibonacci heaps and their uses in improved network optimization algorithms}}
\item \href{https://epubs.siam.org/doi/10.1137/0218069}{\textcolor{blue}{1989: H Gabow, R Tarjan; Faster Scaling Algorithms for Network Problems}}
\item \href{https://link.springer.com/chapter/10.1007\%2F3-540-48481-7_38}{\textcolor{blue}{1999: M Kao, T Lam, W Sung, H Ting; A Decomposition Theorem for MaximumWeight Bipartite Matchings with Applications to Evolutionary Trees}}
\item \href{https://epubs.siam.org/doi/10.1137/S0097539799361208}{\textcolor{blue}{2001: M Kao, T Lam, W Sung, H Ting; A Decomposition Theorem for Maximum Weight Bipartite Matchings}}
\item \href{https://link.springer.com/chapter/10.1007\%2F978-3-319-06089-7_22}{\textcolor{blue}{2014: S Das, K Kapoor; Fine-Tuning Decomposition Theorem for Maximum Weight Bipartite Matching}}
\end{itemize}
\newpage
\section{Unweighted Maximum Matching in General Graphs}
\begin{itemize}
\item \href{https://link.springer.com/chapter/10.1007/978-0-8176-4842-8_26}{\textcolor{blue}{1965: J Edmonds; Paths, Trees and Flowers}}
\item \href{https://dl.acm.org/doi/10.1145/321941.321942}{\textcolor{blue}{1972: H Gabow; An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs}}
\item \href{https://link.springer.com/article/10.1007/BF02239502}{\textcolor{blue}{1974: T Kameda, I Munro; A O($|V||E|$) algorithm for maximum matching of graphs}}
\item \href{https://dl.acm.org/doi/10.1109/SFCS.1975.5}{\textcolor{blue}{1975: S Even, O Kariv; An O($N^{2.5}$) algorithm for maximum matching in general graphs}}
\item \href{https://dl.acm.org/doi/10.1109/SFCS.1980.12}{\textcolor{blue}{1980: S Micali, V Vazirani; An O($\sqrt{|V|}|E|$) algoithm for finding maximum matching in general graphs}}
\end{itemize}
\section{Completely Distributed Algorithms}
It is interesting to note that completely distributed maximum matching algorithms which have no sequential counterpart were not found. One of the reason could be that all these algorithms make use of the fact that a matching would have an augmenting path in case it is not maximum which is a property of the graph that turns up at a global level.
\chapter*{References}
All the references used to create this report are listed below. The references are hyperlinks.
\begin{enumerate}
\item \href{https://people.eecs.berkeley.edu/~aydin/matchingGraft.pdf}{\textcolor{blue}{Ariful Azad, Aydin Buluc, Alex Pothen (2015); A Parallel Tree Grafting Algorithm for Maximum Cardinality Matching in Bipartite Graphs}}
\item \href{https://link.springer.com/article/10.1007\%2FBF01840395}{\textcolor{blue}{Michael M. Wu; Michael C. Loui (1990). An efficient distributed algorithm for maximum matching in general graphs}}
\item \href{https://en.wikipedia.org/wiki/Hopcroft\%E2\%80\%93Karp_algorithm}{\textcolor{blue}{Wikipedia Article on the Hopcroft-Karp Algorithm}}
\item \href{https://en.wikipedia.org/wiki/Blossom_algorithm}{\color{blue} Wikipedia Article on the Blossom Algorithm}
\item \href{https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf}{\color{blue} Amy Shoemaker \& Sagar Vare (2016); Edmond's Blossom Algorithm}
\item \href{http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf}{\textcolor{blue}{Dr. Mordecai J Golin; Notes on the Hungarian Algorithm}}
\item \href{https://en.wikipedia.org/wiki/Hungarian_algorithm}{\textcolor{blue}{Wikipedia Article on the Hungarian Algorithm}}
\item \href{https://baoilleach.blogspot.com/2017/08/my-acs-talk-on-kekulization-and.html}{\textcolor{blue}{Noel O'Boyle, John Mayfield (2017); ACS Talk}}
\item \href{https://arxiv.org/pdf/1411.1919.pdf}{\textcolor{blue}{R Duan, S Pettie, H Su (2014); Scaling Algorithms for Weighted Matching in General Graphs}}
\item \href{https://www.researchgate.net/publication/343998266_A_Modified_Decomposition_Algorithm_for_Maximum_Weight_Bipartite_Matching_and_Its_Experimental_Evaluation}{\textcolor{blue}{S Das (2020); A Modified Decomposition Algorithm for Maximum Weight Bipartite Matching and Its Experimental Evaluation}}
\end{enumerate}
\end{document}