کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420742 | 683976 | 2006 | 13 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Fast algorithms for identifying maximal common connected sets of interval graphs Fast algorithms for identifying maximal common connected sets of interval graphs](/preview/png/420742.png)
Given a family of interval graphs F={G1=(V,E1),…,Gk=(V,Ek)}F={G1=(V,E1),…,Gk=(V,Ek)} on the same vertices V , a set S⊂VS⊂V is a maximal common connected set of F if the subgraphs of Gi,1⩽i⩽k,Gi,1⩽i⩽k, induced by S are connected in all GiGi and S is maximal for the inclusion order. The maximal general common connected set for interval graphs problem (gen-CCPI) consists in efficiently computing the partition of V in maximal common connected sets of F . This problem has many practical applications, notably in computational biology. Let n=|V|n=|V| and m=∑i=1k|Ei|. For k⩾2k⩾2, an algorithm in O((kn+m)logn)O((kn+m)logn) time is presented in Habib et al. [Maximal common connected sets of interval graphs, in: Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, vol. 3109, Springer, Berlin, 2004, pp. 359–372]. In this paper, we improve this bound to O(knlogn+m)O(knlogn+m). Moreover, if the interval graphs are given as k sets of n intervals, which is often the case in bioinformatics, we present a simple O(knlog2n) time algorithm.
Journal: Discrete Applied Mathematics - Volume 154, Issue 12, 15 July 2006, Pages 1709–1721