Homework 10

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


  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