文献

J-GLOBAL ID：201702269769200435   整理番号：17A1211339

凸特性,Fibonacci数と指数時間アルゴリズムに関するノート【Powered by NICT】

A note on convex characters, Fibonacci numbers and exponential-time algorithms

著者 (2件)： Kelk Steven (Department of Data Science and Knowledge Engineering (DKE), Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands) ,  Stamoulis Georgios (Department of Data Science and Knowledge Engineering (DKE), Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands)
資料名： Advances in Applied Mathematics  (Advances in Applied Mathematics)
巻： 84  ページ： 34-46  発行年： 2017年 
JST資料番号： W1598A  ISSN： 0196-8858  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 系統樹は進化をモデル化するために使用した葉は,現在の種(「分類」)を表現するために標識し,内部頂点が絶滅した祖先を示した。非公式には,凸特性は,与えられた状態を共有する種(現代および絶滅の両方)のサブセットは連結部分木を形成する現代種に測定した。n≧2分類群のセットに無根,二成分系統樹Tが与えられたとき,T上の凸文字の数のための閉(しかしかなり不透明)発現は1992年以来知られており,これはTの正確なトポロジーとは無関係であった。本注記において,筆者らはこの数が実際に(2 n 1)次Fibonacci数に等しいことを証明した。次に,各状態は少なくともk個の分類群に現れるT上の凸文字の数であることg k(T)を定義した。やや奇妙,2g(T)は,Tのトポロジーに依存し,(n 1)次Fibonacci数に等しいであることを示した。ここで示すように,このトポロジー的中立性は,k≧3に対しては成り立たない。しかし,各固定k≧1,g k(T)は,O(n)時間で計算できる,計数特性のセットを効率的に列挙し,サンプリングできることを示した。時間Θ(φ n n 2),φ≒1.618が黄金比で動作するNP困難最大節約距離問題,および時間Θ(Φ2nポリ(n))における樹木二分と再結合距離(最大一致森林)を計算する正確なアルゴリズムのための簡単だが効果的な厳密なアルゴリズムを与え,φ2≒2.619)にこれらの洞察を用いた。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： NP困難 ,  モデリング ,  位相幾何学 ,  *凸形 ,  核間距離 ,  部分集合 ,  *アルゴリズム ,  系統樹
準シソーラス用語： 計数 ,  分類群 ,  部分木 , 【Automatic Indexing@JST】

著者キーワード (6件)： Fibonacci数 ,  Phylogenetics ,  ツリー ,  Convexity ,  計数 ,  Algorithms

分類 (1件)： 進化論一般  (EC03010Q)

タイトルに関連する用語 (4件)： 凸 ,  指数 ,  アルゴリズム ,  ノート