CSC 344
Homework 2

Assigned Feb 26, due Mar 12

Problems from the textbook
A problem from another textbook:

Recall the definition of a connected graph. In this problem we'll study how securely connected a graph is. (For example, if we think of the graph as representing a computer network, could an enemy disconnect the network by sabotaging a single computer or communication link?)

A bridge edge is defined as an edge which, if removed, would leave a disconnected graph.

An articulation point is defined as a vertex which, if removed (with all its incident edges) would leave a disconnected graph.

Write and analyze an efficient algorithm which takes in an undirected, connected graph and finds all its bridge edges. (3 points)

Write and analyze an efficient algorithm which takes in an undirected, connected graph and finds all its articulation points. (3 points)

For both of these, you'll get partial credit for a correct but inefficient algorithm.

Hint: It may help to start by drawing a graph with a single bridge edge or an articulation point, run a breadth-first or depth-first search on it, and see what's special about the bridge edge or articulation point. Then try one with two bridge edges or two articulation points....


Last modified: Mon Feb 26 08:58:18 EST 2007
Stephen Bloch / sbloch@adelphi.edu