お知らせ 2023年度・2024年度 学生員 会費割引キャンペーン実施中です
お知らせ 技術研究報告と和文論文誌Cの同時投稿施策(掲載料1割引き)について
お知らせ 電子情報通信学会における研究会開催について
お知らせ NEW 参加費の返金について
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 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

研究会情報
研究会 CAS  
開催期間 2013-01-28 - 2013-01-29 
開催地(和) 別府国際コンベンションセンター 
開催地(英) Beppu International Convention Center 
テーマ(和) 一般 
テーマ(英) General 
講演論文情報の詳細
申込み研究会 CAS 
会議コード 2013-01-CAS 
本文の言語 日本語 
タイトル(和) 格子グラフ上の二重入れ子状矩形境界間を接続する互いに点素なパスについて 
サブタイトル(和)  
タイトル(英) On Pairwise Vertex-Disjoint Paths Linking Two Nested Rectangular Boundaries in a Rectilinear Graph 
サブタイトル(英)  
キーワード(1)(和/英) 二重入れ子状矩形 / Two nested rectangles  
キーワード(2)(和/英) 点素なパス / Vertex-disjoint paths  
キーワード(3)(和/英) 格子グラフ / Rectilinear graphs  
キーワード(4)(和/英) 配線問題 / Routing Problems  
キーワード(5)(和/英) プリント基板レイアウト / Printed wiring boards layouts  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 花田 英人 / Hideto Hanada / ハナダ ヒデト
第1著者 所属(和/英) 広島大学 (略称: 広島大)
Hiroshima University (略称: Hiroshima Univ.)
第2著者 氏名(和/英/ヨミ) 高藤 大介 / Daisuke Takafuji / タカフジ ダイスケ
第2著者 所属(和/英) 広島大学 (略称: 広島大)
Hiroshima University (略称: Hiroshima Univ.)
第3著者 氏名(和/英/ヨミ) 田岡 智志 / Satoshi Taoka / タオカ サトシ
第3著者 所属(和/英) 広島大学 (略称: 広島大)
Hiroshima University (略称: Hiroshima Univ.)
第4著者 氏名(和/英/ヨミ) 渡邉 敏正 / Toshimasa Watanabe / ワタナベ トシマサ
第4著者 所属(和/英) 広島大学 (略称: 広島大)
Hiroshima University (略称: Hiroshima Univ.)
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者 第1著者 
発表日時 2013-01-28 13:50:00 
発表時間 20分 
申込先研究会 CAS 
資料番号 CAS2012-73 
巻番号(vol) vol.112 
号番号(no) no.418 
ページ範囲 pp.41-45 
ページ数
発行日 2013-01-21 (CAS) 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会