ツリー封じ込め問題に対するQUBO定式化【JST・京大機械翻訳】

Dinneen Michael J.; Ghodla Pankaj S.; Linz Simone

プレプリント

J-GLOBAL ID：202202210257168386 整理番号：22P0293846

ツリー封じ込め問題に対するQUBO定式化【JST・京大機械翻訳】

A QUBO formulation for the Tree Containment problem

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2022年02月22日プレプリントサーバーでの情報更新日： 2022年10月12日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

系統(進化)樹木およびネットワークは,種,言語,癌細胞およびウイルスのような実体間の進化的関係を表現するために広く用いられている葉標識グラフである。系統発生ネットワークを再構築し,解析するために,与えられた根付系統樹が与えられた根付系統樹を埋め込むかどうかを決定する問題は,興味を引いている。この問題は,ツリー格納として形式的に知っていて,一般的でNP完全であり,あるクラスの系統発生ネットワークに対して多項式時間可解性である。本論文では,量子コンピューティングと系統学からアイデアを接続し,一般的設定におけるツリー格納のための効率的な二次制約付き二値最適化定式化を提示した。Nがn_N頂点とTの系統ネットワークである木 Conの例(N,T)は,n_T頂点を持つ系統樹であり,著者らの定式化に必要な論理的量子ビットの数はO(n_Nn_T)である。【JST・京大機械翻訳】

, , , , , , , , , , ,
, , , , 【Automatic Indexing@JST】

グラフ理論基礎 , 分子・遺伝情報処理 , 計算理論

前のページに戻る