摘要 當來自不同來源的同一類群的解析不佳的資訊需要協調時，尋找具有共同葉集 L 的一組有根樹的共同細化的

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

• SFI 頁面

論文資訊

• 類型：已發表論文
• 日期：2022-09-02

摘要

當來自不同來源的同一類群的解析不佳的資訊需要協調時，尋找具有共同葉集 L 的一組有根樹的共同細化的問題自然出現在數學系統發生學中。這構成了經過深入研究的超級樹問題的特殊情況，其中輸入樹的葉集可能不同。解決有根樹相容性問題的演算法當然適用於這種特殊情況。然而，它們需要複雜的輔助資料結構，對於 k 個輸入樹來說，運行時間至少為 O(k|L| log2(k|L|))。在這裡，我們證明可以使用稱為 LinCR 的簡單自下而上演算法在 O(k|L|) 時間內解決該問題。 LinCR 在 Python 中的實作可以在 上免費取得。