Homework 10

Due Friday, February 281 at 5:00 PM. Please refer to the homework policy here.

Problems

  1. Let be an undirected graph with edges and vertices, and let be three distinct vertices. Design and analyze an algorithm that computes a path from to that goes through .
  2. A cycle cover of a directed graph is a collection of vertex-disjoint cycles that covers all the vertices. Describe and analyze an efficient algorithm to find a cycle cover for a given graph, or correctly report that no cycle cover exists. 2

1 Because I was late
2 Hint: bipartite matching