ある種のグラフ問題に対するsearchとdecisionのギャップについて

スポンサーリンク

概要

• 論文の詳細を見る

• 本稿では、あるグラフの性質に対し、与えられたあるグラフがその性質を満たすか否かのみを"yes"か"no"で答える決定問題と、与えられたあるグラフがその性質を満たすならば、その証拠となる解を発見する探索問題のギャップについて考察する。ここで考えられる性質は、k-COLORABILITY,k-BANDWIDTH,とk-UNIFORM EMULATION ON A PATHである。本稿では、探索問題を解く際に決定問題の情報が使える時、そのギャップが高々O(n^2)しかないことを示す。

• 社団法人電子情報通信学会の論文
• 1995-07-27

著者

• 山崎 浩一

  電気通信大学情報工学科

関連論文

• k-ツリーを用いたP^k_nの新しい特徴付け
• NP完全なブール関数に対する多項式時間スライス関数について(計算モデルと計算の複雑さに関する研究)
• restricted RNLC グラフ言語の学習(計算量理論の諸相 : その基礎的研究)
• ある種のNLCグラフ文法によるグラフの集合の学習
• 量子情報理論とその応用論文小特集の発行にあたって(量子情報理論とその応用)
• Some Results for Cluster Traveling Salesperson Problem
• ある拡張された巡回セールスマン問題について
• The algorithmic aspect of "probabilistic method independent number theorem"
• ある種のグラフ問題に対するsearchとdecisionのギャップについて

スポンサーリンク