MINIMUM DIRECTED BANDWIDTH

• 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