Computer Science – Data Structures and Algorithms
Scientific paper
2009-06-10
Computer Science
Data Structures and Algorithms
Scientific paper
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.
Furer Martin
Gaspers Serge
Kasiviswanathan Shiva Prasad
No associations
LandOfFree
An Exponential Time 2-Approximation Algorithm for Bandwidth does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Exponential Time 2-Approximation Algorithm for Bandwidth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Exponential Time 2-Approximation Algorithm for Bandwidth will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-207449