Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM BANDWIDTH

• INSTANCE: Graph $G=\left(V,E\right)$.

• SOLUTION: A linear ordering of V, i.e. a one-to-one function $f:V \rightarrow \{1,2,\ldots,\vert V\vert\}$.

• MEASURE: The bandwidth of the ordering, i.e. $\max_{(u,v) \in E}\vert f(u)-f(v)\vert$.

  
  

• Bad News: Not approximable within 1.5$-\varepsilon$ for any $\varepsilon >0$ [81]. Not approximable with an absolute error guarantee of $\vert V\vert^{1-\varepsilon }$ for every $\varepsilon >0$ [295].

• Comment: Approximable within 3 if every vertex has degree $\Theta(\vert V\vert)$ [296]. Approximable within $O(\log \vert V\vert)$ if G is a caterpillar [234]. Approximable within 2 if G is asteroidal triple-free [326]. Not approximable within 1.332$-\varepsilon$ for any $\varepsilon >0$ if G is a tree [81].

• Garey and Johnson: GT40