根付き部分木プルーンおよび再移植距離のための巡回発電機および改良型線形カーネル【JST・京大機械翻訳】

Kelk Steven; Linz Simone; Meuwese Ruben

プレプリント

J-GLOBAL ID：202202215848084833 整理番号：22P0292516

根付き部分木プルーンおよび再移植距離のための巡回発電機および改良型線形カーネル【JST・京大機械翻訳】

Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance

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

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

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

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

2つの根付き2元系統樹間の根付きサブツリー剪定と再移植(rSPR)距離は,NP困難であるトポロジー非類似性のよく研究された尺度である。ここでは,この問題に対する改良線形カーネルを記述した。特に,古典的サブツリーと連鎖縮小ルールが連鎖縮小ルールの修正型で拡張されるならば,得られたツリーは,kがrSPR距離である,ほとんどの9k-3葉で有ることを示した。そして,この限界は緊密である。以前の最良線形カーネルはサイズO(28k)を有した。この改善を達成するために,著者らは,系統ネットワーク文献で使用される発電機の環状アナログとみなすことができる環状発電機を導入した。著者等の主な結果に対する共ロールとして,著者らはまた,2つの根付き二値系統樹に関する最小ハイブリダイゼーション問題のための改良加重線形カーネルを与えた。【JST・京大機械翻訳】

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

グラフ理論基礎 , 計算理論

, , , , , , ,

前のページに戻る