Content deleted Content added
m dab link |
|||
Line 37:
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 {{harv|Dubey|Feige|Unger|2010}}. 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">
{{cite journal
| author = Ilya Safro and Dorit Ron and Achi Brandt
| title = Multilevel Algorithms for Linear Ordering Problems
| journal = ACM Journal of Experimental Algorithmics
| year = 2008
| pages = 1.4–1.20
| volume = 13
}}</ref>.
==Applications==
| |||