## 140 - Bandwidth

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
I solve 140(Bandwidth) by permutating all pattern and calculate the bandwidth.
But I think this is really slow, can anyone tell me the quick algorithm to solve 140?
Thanks a lot!

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
Unfortunately, there is no quick solution to this problem.

Backtracking with good cutoffs is probably efficient enough.

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
Is there any trick in this problem? I should generate all the permutation, and select that one with the minimum bandwith what is the first in lexicaly oreder. But why my program gets WA? Because of the blank graphs/lines? What sould I print if there is one?
-> 0
Is it ok?

Lawrence
New poster
Posts: 17
Joined: Sat Feb 09, 2002 2:00 am
Location: China
Contact:
How fast would you want? My complete search algorithm only runs 0.47 sec, this is enough for me.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
I permutate and then check the bandwidth. It takes forever since my bandwidth checker is O(26^2). Any ideas on how to check bandwidth faster?

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Well, the first thing to do is to go down to O(8^2) by renaming the nodes to A,B,C,... consecutively. Then, you can gain some speedup if you build the permutations recursively and while building them already partly calculate the bandwith. Of course this also works in the iterative version, but only if you do it yourself rather than to rely on next_permutation of the STL.

If you want it really fast, you should have a look at the programs Skiena mentions in his book. Reportedly you can solve cases with 30 nodes in about a second or a minute, I don't remember.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
You mean the Algorithm Design Manual? I will check it out when I get back from Cali. Thanks for the tip.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Yes, that's the one I meant. You can get a small part of it here:
http://www.cs.sunysb.edu/~algorith/file ... idth.shtml

You can also find two implementations of solutions there, I believe from his students. And at least one of them contains a little documentation of the used algorithm somewhere.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
Just to clarify, I have the book and have read it several times. I was trying to devise a novel algorithm:P

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

### 140 - bandwith

is sample output for problem 140 correct? or just only to show the right output format? i was curios since (correspond to sample input) node F is not adjacent of node C, but the sample output gives F after C.
thank you very much.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Titid, ... you misunderstood the problem. The sample output is correct. You're asked to print the optimal ordering of the nodes, ... you need to understand the pictures that describe ABCDEHGF and ABCDGFHE orderings ...

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
aha, I see, yes i misunderstood the problem, i got AC, thank you pak haryanto.

ivec
New poster
Posts: 8
Joined: Tue May 27, 2003 2:41 pm
Contact:

### 140 - Bandwidth

I had no luck on this one so far... first problem I seem to stumble on.
What would be a good approach?

Googling lead me to consider some "cuthill-mckee" algorithm, but I haven't been able to find a description of that algorithm online. Does anyone have such a description ?
Also, I'm not sure if the algorithm can easily find the lexicographically smallest solution.

So, at this stage, I would really be thankful for any links to some reference and/or hints towards a working approach.

TIA! -- Ivan

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
I think this problem is NP... so your best hope is brute-force with some pruning...

dennis
New poster
Posts: 5
Joined: Fri Aug 01, 2003 4:41 am
Contact:

### 140

Can anyone help me with this problem?
thx for any hints