Abstract
最小共同上界（Least Common Upper Bound，簡稱LCUB）問題是本篇論文中所研究的方向。此問題是最小共同祖先（Least Common Ancetsers， 簡稱LCA）的推廣問題，所不同的是其解可能不只是單一。 這篇論文在bipartite permutation graphs上討論LCUB之問題。我們將針對此問題提出兩個演算法。第一個演算法是給定G和G上的三個點r,a,b後，找出a,b以r為root時的最小共同上界。這個演算法需要花費O(n) time。另外，若我們給定G和G上的一個點r後，想找出G中任兩個點以r作root的最小共同上界。此問題套用上面第一個演算法時，可以在O(n3)的時間內求出，但我們在此提出一個最佳化的演算法，它可以在O(n2)時間內解決這個問題。