Minimum Bandwidth Problem

I'm interesting the NP-complete "minimum bandwidth" problem for finding the minimum bandwidth of a graph. For those not familiar, here is a link about it...

http://en.wikipedia.org/wiki/Graph_bandwidth

I've implemented the Cuthill-McKee algorithm, and this was very successful at giving me a permutation of the vertices in which the bandwidth was reduced; however, I'm looking for the minimum bandwidth, not just a reduced bandwidth that is close. If any of you have experience with this problem, what algorithms provide solutions that are the minimum and not just reduced? I don't need actual implementation of any algori开发者_StackOverflowthm, I just want suggestions for what algorithms to research that yield actual minimum bandwidths.

That's interesting problem, but when I read Wiki (your link):

Both the unweighted and weighted versions are special cases of the quadratic bottleneck assignment problem. The bandwidth problem is NP-hard, even for some special cases.[4] Regarding the existence of efficient approximation algorithms, it is known that the bandwidth is NP-hard to approximate within any constant, and this even holds when the input graphs are restricted to caterpillar trees (Dubey, Feige & Unger 2010). On the other hand, a number of polynomially-solvable special cases are known.

So wiki says it's NP-Hard to approximate it with any constant (So there is no PTAS for this problem) and your chance is just use heuristic algorithms, sure brute force algorithm works, (numbering node with numbers between 1..n randomly in startup, after that use brute force) but you should spend 1000 year to solve it for caterpillar. You should search for heuristic algorithms, not approximation and exact algorithms.

As it is NP complete you have to use some kind of "brute force" algorith. So mainly you have the different brute force as option, e.g. like branch-and-bound or linear programming (its LIP, so its in NP).

As it is NP complete you can also take every solution to a different NP complete problem (TSP, SAT,...) by transforming the problem instance from the NP-completeness proof, apply the algorith, and transform it back.

The simplest improvement you can do, is probably to take the result of your Cuthill-McKee algorithm and throw Tabu Search on it.

See this answer for an overview on some of the algorithms that can be applied.