本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
背景：超級樹問題，即找到一組有根樹的共同細化的任務是數學系統發育學中的重要主題。已知公共葉集 L 的特殊情況可在線性時間內求解。現有方法使用其他輸入樹的資訊來細化一棵輸入樹，然後測試結果是否同構。結果：提出了一種 O(k 垂直條 L 垂直條)演算法 LinCR，用於建構具有公共葉集 L 的 k 個輸入樹的公共細化 T，該演算法以自下而上的方法明確計算 T 的父函數。結論：LinCR 比該問題的其他漸近最優演算法更容易實現，並且在經驗比較中優於替代方案。