Graph bandwidth: Difference between revisions

Revision as of 12:39, 12 February 2016

Revision as of 12:45, 12 February 2016

Line 47:

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}}.

For the case of dense graphs, a 3-approximation algorithm was designed by {{harvtxt|Karpinski, |Wirtgen & |Zelikovsky (|1997)}}.<ref>{{Cite journal

| last1 = Karpinski | first1 = Marek

| last2 = Wirtgen | first2 = Jürgen

| last3 = Zelikovsky | first3 = Aleksandr

| title = An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

| journal = Electronic Colloquium on Computational Complexity

| volume = 4 | number = 17

| year = 1997

| url = http://eccc.hpi-web.de/report/1997/017/

}}</ref>

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

Line 146 ⟶ 137:

| last2 = Shamir | first2 = Ron

| doi=10.1137/s0097539793258143}}

*{{Cite journal

*

| last1 = Karpinski | first1 = Marek

| last2 = Wirtgen | first2 = Jürgen

| last3 = Zelikovsky | first3 = Aleksandr

| title = An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

| journal = Electronic Colloquium on Computational Complexity

| volume = 4 | number = 17

| year = 1997

| url = http://eccc.hpi-web.de/report/1997/017/

}}

==External links==