  The bandwidth of a graph G on n vertices is the minimum b such that the
vertices of G can be labeled from 1 to n such that the labels of every pair of
adjacent vertices differ by at most b.
  In this paper, we present a 2-approximation algorithm for the bandwidth
problem that takes worst-case O(1.9797^n) time and uses polynomial space. This
improves both the previous best 2- and 3-approximation algorithms of Cygan et
al. which have an O(3^n) and O(2^n) worst-case time bounds, respectively. Our
algorithm is based on constructing bucket decompositions of the input graph. A
bucket decomposition partitions the vertex set of a graph into ordered sets
(called buckets) of (almost) equal sizes such that all edges are either
incident to vertices in the same bucket or to vertices in two consecutive
buckets. The idea is to find the smallest bucket size for which there exists a
bucket decomposition. The algorithm uses a simple divide-and-conquer strategy
along with dynamic programming to achieve this improved time bound.

Data Structures and Algorithms;Discrete Mathematics