  We deal with exact algorithms for Bandwidth, a long studied NP-hard problem.
For a long time nothing better than the trivial O*(n!) exhaustive search was
known. In 2000, Feige an Kilian came up with a O*(10^n)-time algorithm.
Recently we presented algorithm that runs in O*(5^n) time and O*(2^n) space..
  In this paper we present a major modification to our algorithm which makes it
run in O(4.83^n) time with the cost of O*(4^n) space complexity. This
modification allowed us to perform Measure & Conquer analysis for the time
complexity which was not used for such types of problems before.

Computational Complexity;Data Structures and Algorithms