maximum degree at most ∆, a similar bound holds (cf. ): Computing the bandwidth Both the unweighted and weighted versions are special cases of the quadratic bottleneck assignment problem. The bandwidth problem is NP-hard, even for some special cases. Regarding the existence of efficient approximation algorithms, it is known that the bandwidth is NP-hard to approximate within any constant, and this even holds when the input graphs are restricted to caterpillar trees with maximum hair length 2 . For the case of dense graphs, a 3-approximation algorithm was designed by . On the other hand, a number of polynomially-solvable special cases are known. A heuristic algorithm for obtaining linear graph layouts of low bandwidth is the Cuthill–McKee algorithm. Fast multilevel algorithm for graph bandwidth computation was proposed in. Applications The interest in this problem comes from some application areas. One area is sparse matrix/band matrix handling, and general algorithms from this area, such as Cuthill–McKee algorithm, may be applied to find approximate solutions for the graph bandwidth problem. Another application domain is in electronic design automation. In standard cell design methodology, typically standard cells have the same height, and their placement is arranged in a number of rows. In this context, graph bandwidth problem models the problem of placement of a set of standard cells in a single row with the goal of minimizing the maximal propagation delay (which is assumed to be proportional to wire length). See also Pathwidth, a different NP-complete optimization problem involving linear layouts of graphs. References External links Minimum bandwidth problem, in: Pierluigi Crescenzi and Viggo Kann (eds.), A compendium of NP optimization problems. Accessed May 26, 2010. Graph algorithms Combinatorial optimization NP-hard problems Graph invariants