Content deleted Content added
major discovery |
The referenced article for caterpilar tree uses a different definition than the mentioned paper. The definition from the other article allows for a very simple algorithm. The bandwidth of such a caterpilar tree according to the algorithm is just maximum degree + 1. |
||
Line 46:
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.<ref>Garey–Johnson: GT40</ref> Regarding the existence of efficient
[[approximation algorithm]]s, it is known that the bandwidth is [[hardness of approximation|NP-hard to approximate]] within any constant, and this even holds when the input graphs are restricted to [[caterpillar tree]]s with maximum hair length 2 {{harv|Dubey|Feige|Unger|2010}}.
For the case of dense graphs, a 3-approximation algorithm was designed by {{harvtxt|Karpinski|Wirtgen|Zelikovsky|1997}}.
On the other hand, a number of polynomially-solvable special cases are known.<ref name=feige>"Coping with the NP-Hardness of the Graph Bandwidth Problem", Uriel Feige, ''[[Lecture Notes in Computer Science]]'', Volume 1851, 2000, pp. 129-145, {{doi|10.1007/3-540-44985-X_2}}</ref> 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.<ref name="multilevellinord">
| |||