Even Faster Exact Bandwidth

Original · EN

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ⁿ)-time algorithm. Recently we presented algorithm that runs in O*(5ⁿ) time and O*(2ⁿ) space.. In this paper we present a major modification to our algorithm which makes it run in O(4.83ⁿ) time with the cost of O*(4ⁿ) 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.