著者
シュレスタアニシュマンシング 田湯 智 上野 修一
出版者
情報処理学会
雑誌
研究報告アルゴリズム(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.

言及状況

Twitter (1 users, 1 posts, 0 favorites)

こんな論文どうですか? Bandwidth of Convex Bipartite Graphs and Related Graph Classes(シュレスタアニシュマンシング ほか),2010 http://t.co/ApohQgbTEN

収集済み URL リスト