k-集合链域交的森林表示及求解(英文)

k个集合S1,S2 ,… ,Sk的链域交是由所有满足以下条件的k元组 (s1,s2 ,… ,sk)组成的集合 :e( 1)i si-si+1 e( 2 )i ,其中sk ∈Sk,si ∈Si,0 e( 1)i e( 2 )i 是常数( 1 i k - 1 ) .已知的求链域交的算法采用k元组表示k集合的链域交 ,其最坏情况时间复杂度为Ω(k∏ki=1ni) ,其中ni=｜Si｜ ,1 i k .本文采用森林表示k集合的链域交 ,并基于这种表示方法提出了一个求链域交的串行算法 .该算法的最坏情况时间复杂度为Ω( ∑k-1i=1nini+1) ,极大地改进了已知的结果 .