Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am having some difficulty following the concept of shrinking a set of node as given in the paper On the Bottleneck Shortest Path Problem

It says:

Shrinking a set of nodes can be done in linear time. More precisely, given a set S ⊆ V of nodes of an (undirected) graph G = (V,E), one can construct in linear time another graph with nodes (V \S)$\cup${vnew} (where vnew represents the shrunken set S), where v,w ∈ V \ S are adjacent if and only if v and w are adjacent in G (in this case,the edge keeps its weight), and vnew and w ∈ V \ S are adjacent if and only if there is some v ∈ S such that v and w are adjacent in G (in which case the edge receives the biggest weight of any edge connecting S and w in G).

I am particularly confused about the last sentence of how vnew and w are adjacent. Actually I am pretty much confused about it all and any clarity would be appreciated.

share|cite|improve this question
up vote 1 down vote accepted

Draw some graph with vertex set $V$. Mark off a subset of those vertices and call it $S$. You now have two types of vertices: those in $S$ and those outside of $S$, and you have three types of edges: those connecting vertices of $S$, those connecting vertices outside of $S$, and those on the "boundary", connecting vertices of $S$ to vertices outside of $S$.

In the "shrinking" operation, we're removing all the vertices of $S$ and replacing them with a single new vertex which you're calling vnew. Visually, think of squishing all the vertices of $S$ together. So in the new graph all the vertices outside of $S$ stay put and all the vertices in $S$ merge into this new guy vnew.

What happens to the edges?

The edges that used to connect vertices of $S$ among themselves are just gone.

The edges that used to connect two vertices outside of $S$ stay put. Both their ends are still there.

Finally, the boundary edges: each one used to connect some vertex $s$ in $S$ to some vertex $v$ outside of $S$. Quite naturally, such an edge is now replaced by a new one connecting our vnew to $v$.

Thus, if $v$ (outside of $S$) was connected to one or more vertices in $S$, it is now connected to vnew. If there are weights on the edges, the weight of this new edge between $v$ and vnew is taken to be the max of all the weights of edges connecting $v$ to anyone in $S$.

(If $v$ is not connected to anything in $S$, it stays unconnected to vnew).

Does this make sense now?

share|cite|improve this answer

Consider the following example,

Say you had a set of companies and for each pair of companies, you record the maximum number of emails sent by one to the other (i.e For example, when considering exchanges between companies $A$ and $B$ you pick maximum of number of emails from $A$ to $B$, and number of emails from $B$ to $A$)

You can model this as a graph, with the companies as nodes, join two companies by an edge if they had an email exchange. Mark the edge with the maximum number of email sent by one to the other.

Now suppose some companies decided to merge and wanted to form a new company called $vnew$.

How would the graph model change?

For two companies which were not involved in the merger, the edge between them remains the same.

Suppose companies $A,B,C$ were part of the merger, while $D$ was not.

If you now consider the email exchange between $D$ and $vnew$, you need to consider the previous exchange between $D$ and $A$, $D$ and $B$ and $D$ and $C$. Pick the maximum among those three, and create an edge between $D$ and the new company $vnew$ recording that exchange.

Hope that helps.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.