## 3 Polynomial Time Algorithms for the Bandwidth Problem
### Linear Time Algorithm for a Chain Graph
```
Input : Chain graph \(G=(X,Y,E)\) with \(N(x_{n})\subseteq\cdots\subseteq N(x_{1})\) and \(N(y_{1})\subseteq\cdots\subseteq N(y_{n^{\prime}})\) Output : \(\mathsf{bw}(G)\) \(bw:=\mathsf{bw}(H_{0})\) // by Algorithm 2 for\(i=1,2,\ldots,n-1\)do  construct the interval representation \(\mathcal{I}(H_{i})\) of the graph \(H_{i}\) with \(\mathsf{wiper}(x_{i})\); for\(\ell=n,n-1,\ldots,i+1\)do for\(r=1,2,\ldots,n^{\prime}-d(x_{i+1})\)do if\(\max\{|\mathsf{RC}_{i}(\ell,r)|,|\mathsf{CC}_{i}(\ell,r)|,|\mathsf{LC}_{i}(\ell,r)|\}<bw\)then \(bw=\max\{|\mathsf{RC}_{i}(\ell,r)|,|\mathsf{CC}_{i}(\ell,r)|,|\mathsf{LC}_{i} (\ell,r)|\}\); return(\(bw-1\)). ```  
**Algorithm 3**Bandwidth of a chain graph  
Linear time implementation:A straightforward implementation gives \(O((n+n^{\prime})^{3})\) time and \(O(n+n^{\prime})\) space algorithm. We here show how to improve the time complexity to linear time. Intuitively, we maintain the differences of three maximum cliques \(\mathsf{LC}_{i}\), \(\mathsf{CC}_{i}\), and \(\mathsf{RC}_{i}\) efficiently, and we use the same idea as in the proof of Theorem 6 twice. We first fix \(i=1\). In this case, we can compute \(\mathsf{LC}_{1}\), \(\mathsf{CC}_{1}\), and \(\mathsf{RC}_{1}\) in \(O(n+n^{\prime})\) time; the algorithm first starts \(\mathsf{RC}_{1}{}^{\prime}:=\{x_{1},y_{1},\ldots,y_{n^{\prime}-d(x_{2})}\}\), \(\mathsf{CC}_{1}{}^{\prime}:=\{x_{1},y_{n^{\prime}-d(x_{2})+1},\ldots,y_{n^{ \prime}}\}\), and \(\mathsf{LC}_{1}{}^{\prime}:=\{x_{2},\ldots,x_{n},y_{n^{\prime}-d(x_{2})+1}, \ldots,y_{n^{\prime}}\}\). That is, all points in \(X_{2}^{R}(=\{x_{2},\ldots,x_{n}\})\) are extended to the left, and all points in \(Y_{2}^{L}(=Y\setminus N(x_{2}))\) are extended to the right. If \(\max\{|\mathsf{LC}_{1}{}^{\prime}|,|\mathsf{RC}_{1}{}^{\prime}|\}>|\mathsf{CC} _{1}{}^{\prime}|\), the algorithm flips the interval (or updates \(\ell\) or \(r\)) into \(\mathsf{CC}_{1}{}^{\prime}\), decreases \(|\mathsf{LC}_{1}{}^{\prime}|\) or \(|\mathsf{RC}_{1}{}^{\prime}|\), and increases \(|\mathsf{CC}_{1}{}^{\prime}|\). Repeating this process, in \(O(n+n^{\prime})\) time, when the algorithm meets \(\max\{|\mathsf{LC}_{1}|,|\mathsf{RC}_{1}|\}=|\mathsf{CC}_{1}|\) or \(\max\{|\mathsf{LC}_{1}|,|\mathsf{RC}_{1}|\}=|\mathsf{CC}_{1}|-1\), the value gives the minimum size of the maximum cliques in three parts, or equivalently, gives a minimum completion of \(H_{1}\). When we have a minimum completion of \(H_{1}\), we say this pair \((\ell,r)\) is the _best pair_ for \(H_{1}\). Now, we compute \(\mathsf{LC}_{2}\), \(\mathsf{CC}_{2}\), and \(\mathsf{RC}_{2}\) from \(\mathsf{LC}_{1}\), \(\mathsf{CC}_{1}\), and \(\mathsf{RC}_{1}\) with the best pair for \(H_{1}\) in \(O(d(x_{1})-d(x_{3}))\) time. Intuitively, \(H_{2}\) is obtained from \(H_{1}\) by the following steps; (1) remove \(I_{x_{2}}=[1,1]\) from the point 1, and put it as an interval \([0,d(x_{1})]\); (2) shift all positive points \(I_{y_{j}}\) at \(d(x_{1})-j+1\) with \(y_{j}\in N(x_{1})\setminus N(x_{2})\) to \(d(x_{2})-j+1\); and (3) remove all intervals \(I_{y_{j}}=[-1,0]\) with \(y_{j}\in N(x_{2})\setminus N(x_{3})\) and put them at \(d(x_{2})-j+1\) as points. The movements have influences on \(\mathsf{LC}_{1}\), \(\mathsf{CC}_{1}\), and \(\mathsf{RC}_{1}\), and from them, we construct \(\mathsf{LC}_{2}\), \(\mathsf{CC}_{2}\), and \(\mathsf{RC}_{2}\), and obtain the best pair for \(H_{2}\) in a similar way to that used in the proof of Theorem 6. Then, since \(N(x_{3})\subseteq N(x_{2})\subseteq N(x_{1})\), the total difference (or the total number of flipped intervals) can be bounded above by \(|\{x_{2}\}\cup(N(x_{1})\setminus N(x_{2}))\cup(N(x_{2})\setminus N(x_{3}))|=| \{x_{2}\}\cup(N(x_{1})\setminus N(x_{3}))|=d(x_{1})-d(x_{3})+1\). Hence the computation of \(\mathsf{LC}_{2}\), \(\mathsf{CC}_{2}\), and \(\mathsf{RC}_{2}\) from \(\mathsf{LC}_{1}\), \(\mathsf{CC}_{1}\), and \(\mathsf{RC}_{1}\) requires \(O(d(x_{1})-d(x_{3}))\) time.