2
$\begingroup$

In section 17.2 of the book "Combinatorial optimization polyhedra and efficiency" by Schrijver, he describes the Hungarian method for maximum weight matching in bi-partite graphs (with classes $U$ and $W$). He defines for a matching, $M$, $U_M$ and $W_M$ as the set of vertices in $U$ and $W$ missed by $M$. He then says "if there is a $U_M - W_M$ path, find the shortest such path". I'm not sure what this means. How is a path between two sets of vertices defined?

He is describing this path on a directed graph, $D_M$ where all edges in $M$ are directed from $U$ to $W$ and edges not in $M$ are directed from $W$ to $U$.

$\endgroup$
2
$\begingroup$

An $A$-$B$ path is a path that starts at some $a \in A$ and ends at some $b \in B$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.