歩行からの次数限定木推論問題
スポンサーリンク
概要
- 論文の詳細を見る
与えられた文字列が軌跡となる歩行を実現する最小の辺彩色無向グラフ見つける問題を考える.これは,最大次数がk【greater than or equal】3のグラフの族についてはNP完全であること,一方,次数制限なしの木については線形時間で解けることが示されている.本稿では,最大次数がk【greater than orequal】3の木の族についてはNP完全になること,さらに,最大次数3の木の族を(1,1)-キャタピラーというシンプルな木の族に制限してもNP完全であることを示す.
- 社団法人電子情報通信学会の論文
- 1994-10-21
著者
関連論文
- D-8-28 一般化結合ルールのデータマイニングとその近似可能性について
- 正員の例からの最良コンセンサスモチーフの抽出
- アミノ酸配列データからの機械発見システムBONSAI Garden
- 歩行からの次数限定木推論問題
- 最小共通包含木問題に対する並列近似アルゴリズム
- 推論の並列化(計算量理論とその周辺)
- 辞書式順序で最初の極大部分グラフを計算する問題のP完全性とNCアルゴリズム(計算アルゴリズムと計算量の基礎理論)
- 最適degenerate pattern探索アルゴリズムと転写因子結合部位同定問題への適用
- 最適 degenerate pattern 探索アルゴリズムと転写因子結合部位同定問題への適用
- 数学科でバイオインフォマティクス教育に取り組む
- 知識発見システムのためのView Designer
- 並列知識獲得システムBONSAI Garden
- 形式グラフ体系上の反駁木問題の並列化とグラフ同型問題(計算機構とアルゴリズム)
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- Recovery of Incomplete Tables under Data Dependencies (形式言語理論とオ-トマトン理論)
- 歩行を実現するグラフ構成問題について(理論計算機科学とその周辺)
- 並列アルゴリズムの理論
- 並列アルゴリズムの複雑さ
- 並列化とその限界 : 理論的側面から
- 分岐数限定超グラフに対する極大独立集合を求めるNCアルゴリズム
- ゲノム情報における機械学習の計算量 : 理論と実際 (「人工知能技術における計算量」)
- 学習アルゴリズムによるアミノ酸のインデックス化とタンパク質データからの知識獲得実験
- 機械学習理論を適用したアミノ酸配列からの知識獲得
- PAC 学習 : 確率的で近似的に正しい学習 (計算的学習理論とその応用)