Page 1 of 4

Posted: Wed Jan 02, 2002 8:10 pm
by ..
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!

Posted: Thu Jan 03, 2002 11:51 pm
by chrismoh
Unfortunately, there is no quick solution to this problem.

Backtracking with good cutoffs is probably efficient enough.

Posted: Fri Feb 01, 2002 2:07 pm
by ftomi
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?

Posted: Sat Feb 23, 2002 3:56 pm
by Lawrence
How fast would you want? My complete search algorithm only runs 0.47 sec, this is enough for me.

Posted: Wed Apr 17, 2002 11:02 pm
by C8H10N4O2
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?

Posted: Thu Apr 18, 2002 2:16 am
by Stefan Pochmann
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.

Posted: Thu Apr 18, 2002 10:38 am
by C8H10N4O2
You mean the Algorithm Design Manual? I will check it out when I get back from Cali. Thanks for the tip.

Posted: Thu Apr 18, 2002 11:33 am
by Stefan Pochmann
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.

Posted: Mon Apr 22, 2002 1:02 am
by C8H10N4O2
Just to clarify, I have the book and have read it several times. I was trying to devise a novel algorithm:P

140 - bandwith

Posted: Mon Apr 21, 2003 5:21 pm
by titid_gede
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.

Posted: Mon Apr 21, 2003 9:40 pm
by turuthok
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-

Posted: Tue Apr 22, 2003 5:26 pm
by titid_gede
aha, I see, yes i misunderstood the problem, i got AC, thank you pak haryanto.

140 - Bandwidth

Posted: Sat Jun 28, 2003 12:42 am
by ivec
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

Posted: Sun Jun 29, 2003 5:53 am
by junjieliang
I think this problem is NP... so your best hope is brute-force with some pruning...

140

Posted: Sun Aug 10, 2003 6:10 am
by dennis
Can anyone help me with this problem?
thx for any hints