دانلود مقاله ISI انگلیسی شماره 79090
عنوان فارسی مقاله

.

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
79090 2006 13 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Fast algorithms for identifying maximal common connected sets of interval graphs
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Discrete Applied Mathematics, Volume 154, Issue 12, 15 July 2006, Pages 1709–1721

پیش نمایش مقاله
پیش نمایش مقاله .

چکیده انگلیسی

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.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.