TY - JOUR

T1 - An exponential time 2-approximation algorithm for bandwidth

AU - Fürer, Martin

AU - Gaspers, Serge

AU - Kasiviswanathan, Shiva Prasad

N1 - Funding Information:
We thank the reviewers for very helpful comments, in particular to avoid overcounting in the proof of Proposition 3.6. MF acknowledges partial support from the National Science Foundation (CCF-0728921 and CCF-0964655). SG acknowledges partial support from the Norwegian Research Council and the Australian Research Council (DE120101761).

PY - 2013/11/4

Y1 - 2013/11/4

N2 - 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.9797n)=O(30.6217n) time and uses polynomial space. This improves both the previous best 2- and 3-approximation algorithms of Cygan et al. which have O*(3n) and O*(2n) worst-case running 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 divide-and-conquer strategy along with dynamic programming to achieve the improved time bound.

AB - 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.9797n)=O(30.6217n) time and uses polynomial space. This improves both the previous best 2- and 3-approximation algorithms of Cygan et al. which have O*(3n) and O*(2n) worst-case running 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 divide-and-conquer strategy along with dynamic programming to achieve the improved time bound.

UR - http://www.scopus.com/inward/record.url?scp=84887993002&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84887993002&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2013.03.024

DO - 10.1016/j.tcs.2013.03.024

M3 - Article

AN - SCOPUS:84887993002

SN - 0304-3975

VL - 511

SP - 23

EP - 31

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -