| 講演名 | 2000/6/19 COMP2000-20 DNA計算におけるグラフ問題の符号化について 中本 聡, 尾関 博昭, 陳 慰, 和田 幸一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | DNA計算の創始者であるAdlemanは抽出という操作を用いて、ハミルトン経路問題の解法を示した。しかし、抽出の操作はエラー率が非常に大きい。Amosらはエラー率の小さい除去という操作を用いてNP-完全であるグラフ問題に対する解法を示したが、必要となるDNA鎖の量が多くなる。本稿では頂点の順列を初期の解候補として用いるAmosらの手法を改良し、辺によって連結した頂点の列を初期の解候補とする事で、必要なDNA鎖の量を減らすグラフ問題に対する符号化を提案する。また、その方法を用いてハミルトン経路問題と部分グラフ同型問題の解法を示す。 |
| 抄録(英) | Adleman presented the solution of the Hamiltonian path problem with extract operation. But extract has high error probability. Amos et al. presented the solution for some NP-complete graph problems with remove operation. Although remove has very low error probability, we need a large amount of DNA strands to encode the problems. In this paper, we imoprove the method by Amos and propose the encoding for graph problems to reduce amount of DNA. We also present the solution of the Hamiltonian path problem and the subgraph isomorphism problem. |
| キーワード(和) | DNA計算 / グラフ問題 / エラー耐性 |
| キーワード(英) | DNA computing / graph problem / error-resilient |
| 資料番号 | COMP2000-20 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2000/6/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | COMP2000-20 DNA計算におけるグラフ問題の符号化について |
| サブタイトル（和） | |
| タイトル（英） | An Error-resilient Encoding with Less DNA Strands for Graph Problems on DNA Computing |
| サブタイトル（和） | |
| キーワード(1)（和/英） | DNA計算 / DNA computing |
| キーワード(2)（和/英） | グラフ問題 / graph problem |
| キーワード(3)（和/英） | エラー耐性 / error-resilient |
| 第 1 著者 氏名（和/英） | 中本 聡 / Satoshi Nakamoto |
| 第 1 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Nagoya Institute of Technology |
| 第 2 著者 氏名（和/英） | 尾関 博昭 / Hiroaki Ozeki |
| 第 2 著者 所属（和/英） | (現)ソニー美濃加茂株式会社 (Present address)Sony Minokamo Corporation |
| 第 3 著者 氏名（和/英） | 陳 慰 / Chen Wei |
| 第 3 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Nagoya Institute of Technology |
| 第 4 著者 氏名（和/英） | 和田 幸一 / Koichi Wada |
| 第 4 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Nagoya Institute of Technology |
| 発表年月日 | 2000/6/19 |
| 資料番号 | COMP2000-20 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 144 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |