CSE 417 Assignment #4
Autumn 2002

Due: Friday, December 6, 2002.

  1. 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.) Bonus points are available the more efficient your algorithm is. Ideally your algorithm should be linear time.
    Hint: Use the "no cross edges" property of the non-tree edges of the graph given the DFS tree.

  2. Given a connected, weighted, undirected graph G in class we considered the minimum weight spanning tree problem.

    1. Design an algorithm that instead will find a maximum weight spanning tree in such a graph.

    2. Show why your algorithm is correct, give a running time bound and justify this analysis.

    3. (Bonus) For a given network one might want to define an emergency sub-network for connecting all sites. Suppose now that the input graph above represents the network and the weight of an edge represents the probability that the connection represented by the edge will not fail. Given an assumption of independent failures, the probability that no edge of a sub-network fails is the product of the probabilities that its individual edges (connections) do not fail. Show how to use the algorithm given in part (a) to find a sub-network that connects all nodes and has the highest probability of having all its edges working among all such sub-networks.
      (Hint: Consider taking logarithms of the weights.)

  3. Given a graph G=(V,E) the k-core of G is the largest possible sub-graph C of G such that every vertex of C is a neighbor of at least k other vertices in C (and every vertex/edge of C is also a vertex/edge of G.)

    1. Design a 'reverse greedy' algorithm (that greedily throws thing out rather than choosing them) that given a graph G and integer k will find the k-core of G if such a sub-graph exists and return the empty graph otherwise. For full credit your algorithm should run in linear time.

    2. Explain why your algorithm takes only linear time.

    3. Argue that your algorithm is correct and use this to show that there is at most one possible k-core for a given graph (which justifies the use of "the" above).

  4. Build the pattern-matching finite automaton (labeled directed graph) that is the result of preprocessing the pattern abaababaaa.

  5. Skiena's book, page 160, Problem 6-2.

  6. Why is the following not a proof that P is different from NP? We can decide the Satisfiability problem using the following algorithm: Given a formula F in n variables, try all 2n truth assignments and see if there is any assignment that makes F true. If there is one, then output "Yes", else output "No". This algorithm takes at least 2n time in the worst case and since 2n is not polynomial in n, this is not polynomial time.

  7. Skiena' book, page 161, Problem 6-6.

  8. (Bonus) Skiena's book, page 112, Problem 4-13.