| 講演名 | 2002/6/20 禁止領域を持つ格子スタイナー木問題の発見的解法 高藤 大介, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 格子スタイナー木問題とは,格子グラフH=(N,A),禁止領域集合族D={D_i⫅N|D_j∩D_κ=0,1≦j |
| 抄録(英) | The rectilinear Steiner tree problem with a family D of rectangular obstacles D_i(1≦i≦δ) is defined as follows: given a rectilinear graph H=(N,A), a set P⫅N of terminal points, and a family D of rectangular obstacles that are subgraphs of H, find a minimum cost rectilinear Steiner tree connecting P in the graph H-∪_D_i∈DD_i obtained by removing all points from H in D. For D≠0, a fast heuristic algorithm DD_t, which iterates DD t times so as to obtain a better solution without increasing computation time, is proposed, where DD is a fast heuristic algorithm proposed in [3]. Also proposed is a heuristic algorithm DIV_DD_t based on partitioning H into some rectangular regions (rectilinear subgraphs), followed by applying DD_t to each region. Evaluating the performance of these algorithms through experimental results is also given. |
| キーワード(和) | 格子スタイナー木 / 禁止領域 / 発見的解法 / 矩形領域への分割 |
| キーワード(英) | Rectilinear Steiner trees / rectangular obstacles / heuristic algorithms / partitioning rectangular regions |
| 資料番号 | VLD2002-33 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2002/6/20(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 禁止領域を持つ格子スタイナー木問題の発見的解法 |
| サブタイトル（和） | |
| タイトル（英） | Heuristic Algorithms for the Rectilinear Steiner Tree Problem with Obstacles |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 格子スタイナー木 / Rectilinear Steiner trees |
| キーワード(2)（和/英） | 禁止領域 / rectangular obstacles |
| キーワード(3)（和/英） | 発見的解法 / heuristic algorithms |
| キーワード(4)（和/英） | 矩形領域への分割 / partitioning rectangular regions |
| 第 1 著者 氏名（和/英） | 高藤 大介 / Daisuke TAKAFUJI |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Enginnering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 田岡 智志 / Satoshi TAOKA |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Enginnering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 3 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Enginnering, Hiroshima University |
| 発表年月日 | 2002/6/20 |
| 資料番号 | VLD2002-33 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 164 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |