講演抄録/キーワード |
講演名 |
2013-01-28 13:50
格子グラフ上の二重入れ子状矩形境界間を接続する互いに点素なパスについて ○花田英人・高藤大介・田岡智志・渡邉敏正(広島大) CAS2012-73 |
抄録 |
(和) |
格子グラフ上の1つの矩形内部にもう1つの矩形が配置されている状況で,2つの矩形境界間の領域を$G$とする.ここで$m$個の端子対が,任意の端子対の一方は外側の矩形境界上に,他方は内側の矩形境界上に存在する形で与えられているとする.本稿では,$G$上でこれらの端子対間を接続する,互いに点素なパスを求める$O(m^2 +
k)$時間解法を提案する.ここで,$k$は$G$の頂点数である.しかし,提案する解法の正当性は証明できていない.本稿の結果はプリント基板レイアウト設計における配線問題解法に応用がある. |
(英) |
In a rectilinear graph, a rectangle is fixed in another rectangle.
The region bounded by two nested rectangles is $G$.
In this paper, we give an $O(m^2 + k)$ time algorithm for finding vertex-disjoint paths linking 2-terminals nets on two nested rectangular boundaries, where $m$ is the number of 2-terminals nets and $k$ is the
number of vertices in $G$. However, the correctness of the algorithm is
not proven.
Our results apply to routing problems on designing printed wiring boards
layout. |
キーワード |
(和) |
二重入れ子状矩形 / 点素なパス / 格子グラフ / 配線問題 / プリント基板レイアウト / / / |
(英) |
Two nested rectangles / Vertex-disjoint paths / Rectilinear graphs / Routing Problems / Printed wiring boards layouts / / / |
文献情報 |
信学技報, vol. 112, no. 418, CAS2012-73, pp. 41-45, 2013年1月. |
資料番号 |
CAS2012-73 |
発行日 |
2013-01-21 (CAS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CAS2012-73 |