CSE 421 Assignment #2
Winter 2003

Due: Friday, January 24, 2003.

Reading Assignment: Kleinberg and Tardos Chapter 2 and also begin reading Chapter 3.

Problems:

1. Kleinberg and Tardos, Section 2.7, Problem 1, page 54
2. Consider depth-first-search on a directed graph G=(V,E), starting from node s. Let T = (V_T, E_T) be the resulting depth-first-search tree. We began a discussion in class of the categories of edges in this graph.

   1. Characterize the set of nodes in V_T.

   2. The edges visited during the depth-first search can be categorized into four categories:

      • tree edges: edges in E_T;

      • forward edges: edges from a node in V_T to a descendent (that is not a child) in V_T;

      • back edges: edges from a node in V_T to an ancestor in V_T;

      • cross edges: edges between nodes in V_T that are unrelated in T.
      Write pseudo-code for DFS(s) that prints out for each edge visited whether or no t it is a tree edge, a forward edge, a back edge or a cross edge.

3. Use the result of DFS to give an algorithm that determines whether or not an undirected graph is edge-biconnected, that is you can remove any one edge and the graph will remain connected. (Another way to say this is that the graph is connected and every edge is on some cycle.) Ideally your algorithm should run in O(n+m) time.

4. Extra credit: Kleinberg and Tardos, Section 2.7, Problem 4, pages 55-56.

5. Extra credit: Feedback on chapter 2 of Kleinberg and Tardos. This should be sent in e-mail to the address cse421-textbook@cs. Your message should contain your name prominently displayed at the start as well as the number of the chapter for which you are providing comments. If you have more than one comment, your comments should be laid out in some form of numbered or bulleted list.