グラフクラスとアルゴリズム

• 上原, 隆平

書誌事項

タイトル別名

• グラフクラス ト アルゴリズム
• Graph Classes and Algorithms

抄録

計算機で扱う問題は, 多くの場合グラフ上の問題として定式化できる.計算量の理論により, これまで多くの問題が"手に負えない"ことが示されてきた.一方でこうした問題に対する現実的なアプローチが幾つか提案されてきた.本稿ではグラフに制限を加えるアプローチについて解説する.DNAの切片間の関係などは, モデル化すると特別なグラフになる.こうしたグラフ上では, これまで手に負えないとされてきた問題が効率良く解けることがある.本稿では, 代表的なグラフクラスと, 関連したアルゴリズムの最近の研究動向を解説する.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/4712

収録刊行物

• 電子情報通信学会誌

  電子情報通信学会誌 88 (2), 118-122, 2005-02-01

  電子情報通信学会

キーワード

• アルゴリズム
• グラフクラス
• 計算の複雑さ
• 理想グラフ

詳細情報

• CRID: 1050001337537161728
• NII論文ID: 110003231917
• NII書誌ID: AN1001339X
• ISSN: 09135693
• NDL書誌ID: 7240055
• Web Site: http://hdl.handle.net/10119/4712
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I7240055
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles