Cheap and Secure Web Hosting Provider : See Now

Understanding the bandwidth problem on graphs

, , No Comments
Problem Detail: 

I'm trying to understand the bandwidth problem on graphs. Consider the following tree given as an adjacency list:

1 => 4 2 => 6 3 => 5, 6 4 => 7 5 => 3 6 => 2, 3, 7 7 => 4, 6 

It is claimed an optimal ordering of the vertices is 1 4 5 7 3 6 2, but I don't see how.

When I draw the graph, 5 is 4 edges away from 4, and 3 edges away from 7... yet we jump back to 7 anyways? I don't understand how this problem works.

Wouldn't the ordering be 1, 4, 7, 6, 2, 3, 5 because everything is one node apart, with a maximum bandwidth of 2, because 2 is 2 edges away from 3? With 1 edge separating everything else.

Bandwidth problem explained in homework assignment:

The bandwidth problem takes as input a graph G, with n vertices and m edges (ie. pairs of vertices). The goal is to find a permutation of the vertices on the line which minimizes the maximum length of any edge. This is better understood through an example. Suppose G consists of 5 vertices and the edges (v1, v2), (v1, v3), (v1, v4), and (v1, v5). We must map each vertex to a distinct number between 1 and n. Under the mapping vi → i, the last edge spans a distance of four (ie. 5-1). However, the permutation {2, 3, 1, 4, 5} is better, for none of the edges spans a distance of more than two. In fact, it is a permutation which minimizes the maximum length of the edges in G, as is any permutation where 1 is in the center

Asked By : Steven

Answered By : Yuval Filmus

I think you got the definition of bandwidth wrong. Here is your definition of the bandwidth of an ordering of the vertices:

The bandwidth is the maximum distance in the graph between adjacent nodes in the ordering.

The correct definition is:

The bandwidth is the maximum distance in the ordering between adjacent nodes in the graph.

Your problem is equivalent to the usual one – just take the inverse of the ordering permutation to get from one to the other.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65901

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback