| 講演名 | 1995/7/27 ある種のグラフ問題に対するsearchとdecisionのギャップについて 山崎 浩一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では、あるグラフの性質に対し、与えられたあるグラフがその性質を満たすか否かのみを"yes"か"no"で答える決定問題と、与えられたあるグラフがその性質を満たすならば、その証拠となる解を発見する探索問題のギャップについて考察する。ここで考えられる性質は、k-COLORABILITY,k-BANDWIDTH,とk-UNIFORM EMULATION ON A PATHである。本稿では、探索問題を解く際に決定問題の情報が使える時、そのギャップが高々O(n^2)しかないことを示す。 |
| 抄録(英) | An algorithm D is a decision algorithm if D decide whether a problem has a explanation or not (D outputs "yes" or "no"). An algorithm S is a search algorithm if S find a explanation for a problem (when the problem has a explanation). A explanation is called a natural evidence. We consider the following three graph problems : k-COLORABILITY, k-BANDWIDTH, and k-UNIFORM EMULATION ON A PATH. In this paper, we discuss the efficiency of finding a natural evidence for the graph problems when its search algorithm can employ its decision algorithm as oracle. We will show that for each the three problem if the decision problem is solvable in time D(n) then the corresponding search problem is solvable in O(n^2×D(n)) time. |
| キーワード(和) | k-COLORABILITY / k-BANDWIDTH / 決定問題 / 探索問題 / 臨界グラフ |
| キーワード(英) | k-COLORABILITY / k-BANDWIDTH / decision problem / search problem / critical graph |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1995/7/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | ある種のグラフ問題に対するsearchとdecisionのギャップについて |
| サブタイトル（和） | |
| タイトル（英） | An approach to acquisition of natural evidence for some graph problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | k-COLORABILITY / k-COLORABILITY |
| キーワード(2)（和/英） | k-BANDWIDTH / k-BANDWIDTH |
| キーワード(3)（和/英） | 決定問題 / decision problem |
| キーワード(4)（和/英） | 探索問題 / search problem |
| キーワード(5)（和/英） | 臨界グラフ / critical graph |
| 第 1 著者 氏名（和/英） | 山崎 浩一 / Koichi Yamazaki |
| 第 1 著者 所属（和/英） | 電気通信大学情報工学科 University of Electro-Communications |
| 発表年月日 | 1995/7/27 |
| 資料番号 | |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 188 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |