Fast algorithms for identifying maximal common connected sets of interval graphs
Given a family of interval graphs F={G1=(V,E1),,Gk=(V,Ek)} F = { G 1 = ( V , E 1 ) ,  , G k = ( V , E k ) } on the same vertices V , a set S?V S ? V is a maximal common connected set of F  if the subgraphs of Gi,1?i?k, G i , 1 ? i ? k , induced by S  are connected in all Gi G i 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 = 1 k | E i | . For k?2 k ? 2 , an algorithm in O((kn+m)logn) O ( ( kn + m ) log n ) 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. 359372]. In this paper, we improve this bound to O(knlogn+m) O ( kn log n + 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 ( kn log 2 n ) time algorithm.
common connected set interval graph comparative genomics umbrella-free ordering