Minimum Cost Perfect Matching

Abstract

This is pseudocode for Minimum Cost Perfect Matching in Bipartite Graphs

.3

Minimum Cost Perfect Matching in Bipartite Graphs

{ } 

InputInputOutputOutput Graph $G$ = ($V$,$E$) with bipartition $U$,$W$ where |$U$| = |$W$| and costs c. A minimum cost perfect matching $M$ or a deficient set $S$

$$\overrightarrow{y_v}:=\frac{1}{2}min\{c_e:e\in E\}$$

(1)

for all $v$ $\in$ $V$ B
Construct graph $H$ with vertices $V$ and edges

$$\{uv\in E:c_{u}v=\overrightarrow{y_u}+\overrightarrow{y_v}\}$$

(2)

$H$ has perfect matching $M$ stop ($M$ is a minimum cost perfect matching of $G$) Let $S$ $\subseteq$ $U$ be a deficient set for $H$ B
all edges of $G$ with an endpoint in $S$ have an endpoint in $N_H$(S) stop ($S$ is a deficient set of G)

$$\in :=min\{c_{uv}-\overrightarrow{y_u}-\overrightarrow{y_v}:uv\in E,u\in S,v\notin N_H(S)\}$$

(3)

$$\overrightarrow{y_v}:=\{\begin{array}{cc}\overrightarrow{y_v}+\in \text{ for }v\in S\hfill & \\ \overrightarrow{y_v}-\in \text{ for }v\in N_H(S)\hfill & \\ \overrightarrow{y_v}\hfill & \end{array}$$

(4)