Homework 4

Due Wednesday, January 29 at 5:00 PM. Please refer to the homework policy here.

  1. A graph is bipartite if the vertices can be partitioned into two subsets and , such that every edge has one vertex in and the other in . Describe and analyze an efficient algorithm that determines whether a given unidrected graph is bipartite.
  2. Suppose we are given a directed acyclic graph with a unique source and a unique sink . A vertex is called an -cut vertex if every path from to passes through , or equivalently, if deleting makes unreachable from . Describe and analyze an algorithm to find every -cut vertex in .