CODEWITHSUNDEEP
algorithmgraph-algorithm
user424603
user424603

Reputation: 1

the shortest even path to minimum weight perfect matching

Given an edge weighted undirected graph and two vertices s and t, weights are non-negative. Shortest Even Path Problem is to find an s,t-path P having an even number of edges whose total weight is as small as possible. How to reduce Shortest Even Path Problem to minimum weight perfect matching problem

Upvotes: 0

Views: 929

Answers (1)

Beta
Beta

Reputation: 99144

Start with the given graph, imagine painting the nodes blue, and call it Gblue. It has nodes, including sblue and tblue, and undirected edges like ablue <-> bblue.

Make a copy of the graph, paint its nodes green and call it Ggreen.

Now reconnect all of the edges, so that ablue<->bblue and agreen<->bgreen (which have equal weights) become ablue<->bgreen and agreen<->bblue (which have the same weights).

In this combined graph, every edge is between a blue node and a green node, so every path alternates between blue and green. So every path from sblue that has a even number of steps, will end on a green node.

Now on this combined graph, seek the minimum-weight path from sblue to tgreen.

Finally, remove the subscripts.

Upvotes: 1

Related Questions