著者

シュレスタアニシュマンシング 田湯 智 上野 修一

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:18840930)

巻号頁・発行日

vol.2010, no.6, pp.1-7, 2010-11-12

---

It is known that the bandwidth problem is NP-complete for chordal bipartite graphs, while the problem can be solved in polynomial time for bipartite permutation graphs, which is a subclass of chordal bipartite graphs. This paper shows that the problem is NP-complete even for convex bipartite graphs, a subclass of chordal bipartite graphs and a superclass of bipartite permutation graphs. We provide polynomial-time approximation algorithms for convex bipartite graphs. We also provide a polynomial-time approximation algorithm for 2-directional orthogonal ray graphs which is a subclass of chordal bipartite graphs and a superclass of convex bipartite graphs.It is known that the bandwidth problem is NP-complete for chordal bipartite graphs, while the problem can be solved in polynomial time for bipartite permutation graphs, which is a subclass of chordal bipartite graphs. This paper shows that the problem is NP-complete even for convex bipartite graphs, a subclass of chordal bipartite graphs and a superclass of bipartite permutation graphs. We provide polynomial-time approximation algorithms for convex bipartite graphs. We also provide a polynomial-time approximation algorithm for 2-directional orthogonal ray graphs which is a subclass of chordal bipartite graphs and a superclass of convex bipartite graphs.