Even Faster Exact Bandwidth
Marek Cygan, Marcin Pilipczuk · ACM Transactions on Algorithms · 2012
We deal with exact algorithms for Bandwidth , a long studied NP-hard problem. For a long time nothing better than the trivial O * ( n !) 1 exhaustive search was known. In 2000, Feige and Kilian [Feige 2000] came up with a O * (10 n )-time and polynomial space algorithm. In this article we present a new algorithm that solves Bandwidth in O * (5 n ) time and O * (2 n ) space. Then, we take a closer look and introduce a major modification that makes it run in O (4.83 n ) time with a cost of a O * (4 n ) space complexity. This modification allowed us to perform the Measure & Conquer analysis for the time complexity which was not used for graph layout problems before.