Description
I. MEASURES OF CONNECTIVITY
A measure of the robustness of a network is the number of edges whose failure prevents network-wide communications. A network is modeled as a graph. The edge-connectivity of a network is the minimum size of a set of
edges the removal of which prevents the network from being connected.
The edge-connectivity of a network is a global parameter. In order to compute the edge-connectivity of a network,
we may start by analyzing the edge-connectivity between pairs of nodes. Oftentimes, the edge-connectivity between
pairs of nodes is interesting in its own right. A set of edges separates a source node from a destination node if
every path from the source to the destination contains at least one edge belonging the set. It is well-known that the
minimum number of edges that separates a source node from a destination node equals the maximum number of
edge-disjoint paths from the source to the destination. A set of paths is edge-disjoint if the paths do not share an
edge.
II. YOUR ASSIGNMENT
What you have to do.
• Design and implement an algorithm to compute the minimum number of edges that separates a source node
from a destination node. The network is given in a file where each line identifies an edge. The source and
destination nodes are given online. You may assume that there are no more than 100 nodes with identifiers
between 0 and 99. (50% of the grade.)
• Given a network in the format above, produce the complementary cumulative distribution of the minimum
number of edges that separates one node from another. That is, for every natural number k, compute the
fraction of pairs of nodes such that more than k edges separates the first node from the second. (25% of the
grade.)
• Given a network in the format above, compute the edge-connectivity of the network. In order to convince a
user of your program that the value presented is the correct one, you should exhibit a set of edges that prevents
the network from being connected. (25% of the grade.)
What do you have to deliver, how, and when.
• You have to deliver your code and a report with a cover page and no more than three other pages containing a
text explanation of your algorithms, their pseudo-codes, their asymptotic complexities, the statistics required,
and a short discussion.
• The code and the report should be sent in a .zip file to my email address with subject p3..zip
where is your group number.
2
• The deadline is December 2, 2016, 23:59.
How I will evaluate your assignment.
• Write your report and your pseudo-code clearly, and present a commented code.
• Be sure to test your code for correctness. I will take into consideration the efficiency of your algorithms.
• I will have a discussion with you about your report and will test your code at the end of the semestre, jointly
with the other assignments.
