| 講演名 | 2007-03-05 回路の端子頂点グラフモデルにおける全域平面部分グラフ抽出法(通信のための信号処理,符号理論,一般) 中西 勝利, 高藤 大介, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では,回路のグラフモデルである端子頂点グラフに対する辺数最大の全域平面部分グラフ抽出問題を扱う.本問題は,NP-困難であることが知られており,既に何種類かの発見的解法が提案されている.これらにいくつかの改良を組込んだ手法を提案し,既存手法とともにそれらの性能を計算機実験により比較評価する。 |
| 抄録(英) | The subject of the paper is the problem of extracting a spanning planar subgraph of maximum cardinality from a terminal-vertex graph that is a graph representation of a given electrical circuit. It is known that this problem is NP-hard. and some heuristic algorithms have already been proposed. The paper proposes heuristic ones by incorporating several improvements into those existing ones. Their performance is evaluated through computation results. |
| キーワード(和) | 部分グラフ抽出 / 全域平面部分グラフ / 端子頂点グラフモデル / 電気回路 |
| キーワード(英) | Subgraph extraction / spanning planar subgraphs / terminal-vertex graph models / electrical circuits |
| 資料番号 | CAS2006-89,SIP2006-190,CS2006-106 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CAS |
|---|---|
| 開催期間 | 2007/2/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Circuits and Systems (CAS) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 回路の端子頂点グラフモデルにおける全域平面部分グラフ抽出法(通信のための信号処理,符号理論,一般) |
| サブタイトル（和） | |
| タイトル（英） | An Algorithm for Extracting a Spanning Planar Subgraph in a Terminal-Vertex Graph Model of a Circuit |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 部分グラフ抽出 / Subgraph extraction |
| キーワード(2)（和/英） | 全域平面部分グラフ / spanning planar subgraphs |
| キーワード(3)（和/英） | 端子頂点グラフモデル / terminal-vertex graph models |
| キーワード(4)（和/英） | 電気回路 / electrical circuits |
| 第 1 著者 氏名（和/英） | 中西 勝利 / Katsutoshi NAKANISHI |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 高藤 大介 / Daisuke TAKAFUJI |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 3 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2007-03-05 |
| 資料番号 | CAS2006-89,SIP2006-190,CS2006-106 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 567 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |