Next: MINIMUM DIRECTED BANDWIDTH Up: Vertex Ordering Previous: Vertex Ordering Index

### MINIMUM BANDWIDTH

- INSTANCE: Graph .

- SOLUTION: A linear ordering of V, i.e. a one-to-one function .

- MEASURE: The bandwidth of the ordering, i.e. .

- Bad News: Not approximable within 1.5 for any [75]. Not approximable with an absolute error guarantee of for every [280].

- Comment: Approximable within 3 if every vertex has degree [281]. Approximable within if G is a caterpillar [217]. Approximable within 2 if G is asteroidal triple-free [309]. Not approximable within 1.332 for any if G is a tree [75].

- Garey and Johnson: GT40