著者

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

出版者

情報処理学会

雑誌

研究報告アルゴリズム(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.

著者

門地 忠夫 田湯 智 金子 峰雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. VLD, VLSI設計技術

巻号頁・発行日

vol.98, no.624, pp.27-34, 1999-03-03

---

デジタル集積回路の動作速度はFFからFFまでの最大信号伝播遅延にてきまる。遅延制御を行なうことでより動作速度を速めることが可能である。本稿では、エルモア遅延モデルを用い、与えられた回路入力によりシンクの最大値延最小化を目指す配線アルゴリズムを提案する。本手法はまず配線の初期界をもとめるために各シンクからソースに対して遠回りせず、かつ総配線長が最小になる配線を生成し、ついでエルモア遅延モデルによる3点問題、4点問題の考察に基づいた配線の生成をおこなう。実験結果はいくつかの入力に対して、実際に得られた遅延の下界に対する割合を示した。