著者

田岡 智志 渡邊 敏正

出版者

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

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.99, no.549, pp.73-80, 2000-01-19

参考文献数

24

---

k辺連結化問題とは、与えられた無向グラフG=(V, E)に付加して得られるグラフG'=(V, E∪E')がk辺連結となるような最小辺集合E'を求める問題である。本稿では、"辺付加により新たに多重辺を作らない"、という条件を加えたk辺連結化問題を扱う。一般には、この問題はNP-hardであり、Gの葉と呼ばれる点集合の総数により問題の難しさが変わることが知られている。本稿では、Gの辺連結度をσとするとき、k=σ+1且つGが2σ+6個未満の葉を持つ場合を考え、リーフグラフの最大マッチングにより生成される葉数と不飽和葉数の関係により、多項式時間の最適解法、あるいは、近似比3 / 2の近似解法、それぞれを提案する。

著者

阿部 健志 渡邊 敏正

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告システムLSI設計技術(SLDM)

巻号頁・発行日

vol.1998, no.10, pp.41-48, 1998-01-30

---

矩形双対グラフを用いたプリント基板レイアウト設計では,各部品矩形内に部品を配置し,部品端子間の配線として,まず,対応する端子矩形間を配線矩形を通るパスで結ぶことを行う.配線を完了するためには,端子矩形まで到達している配線を更に部品矩形内部におかれている部品の実端子まで延長しなければならない.各部品矩形は対応する部品がその内部に配置可能となるような大きさ以上であることは必要である.しかし,前述の配線延長がその内部で可能である形状まで部品矩形の拡大が生じるかもしれない.その際には最小の拡大に抑えることが望まれる.本研究では,いま述べた意味での部品矩形サイズの下界値を求めるために,非交差道を用いた配線領域の見積り手法を提案し,その有効性を実験により評価する.In designing layouts of printed wiring boards with rectangular dualization, layouts are produced by placing elements within corresponding element-rectangles and by routing among terminals. Routing is separated into two stages. The first stage is to obtain wiring among terminal-rectangles. The second stage is done within each element-rectangle and is to find paths, each connecting arm actual pin of the element in this rectangle and the corresponding auxiliary terminal in each terminal-rectangle. The size of each element-rectangle has to be. large enough to make the second stage rotting possible, while this size should be kept as small as possible so that the total size of the board may be minimized. The subject of the paper is to propose a method' of estimating the smallest possible size of a given element-rectangle in which the second stage routing can be completed. Experimental results are provided to show capability of the proposed method.