MINIMUM DIRECTED BANDWIDTH

Next: MINIMUM LINEAR ARRANGEMENT Up: Vertex Ordering Previous: MINIMUM BANDWIDTH Index

INSTANCE: Directed acyclic 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\}$ such that, for all $(u,v) \in E$ , f(u)<f(v).
MEASURE: The bandwidth of the ordering, i.e. $\max_{(u,v) \in E} f(v)-f(u)$ .
Comment: Approximable within 2 if every vertex has indegree $\Theta(\vert V\vert)$ [296].
Garey and Johnson: GT41

Viggo Kann
2000-03-20