کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430876 688219 2014 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computing the rooted triplet distance between galled trees by counting triangles
ترجمه فارسی عنوان
محاسبه فاصله ریشه ای سه گانه بین درختان گلدان با شمارش مثلث ها؟
کلمات کلیدی
الگوریتم نمودار، فاصله ریشه ای سه گانه، مقایسه شبکه فیلوژنتیک، شمارش مثلث، ضرب ماتریس
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We consider a generalization of the rooted triplet distance between two phylogenetic trees to two phylogenetic networks. We show that if each of the two given phylogenetic networks is a so-called galled tree with n   leaves then the rooted triplet distance can be computed in o(n2.687)o(n2.687) time. Our upper bound is obtained by reducing the problem of computing the rooted triplet distance between two galled trees to that of counting monochromatic and almost-monochromatic triangles in an undirected, edge-colored graph. To count different types of colored triangles in a graph efficiently, we extend an existing technique based on matrix multiplication and obtain several new algorithmic results that may be of independent interest: (i) the number of triangles in a connected, undirected, uncolored graph with m   edges can be computed in o(m1.408)o(m1.408) time; (ii) if G is a connected, undirected, edge-colored graph with n vertices and C is a subset of the set of edge colors then the number of monochromatic triangles of G with colors in C   can be computed in o(n2.687)o(n2.687) time; and (iii) if G is a connected, undirected, edge-colored graph with n vertices and R   is a binary relation on the colors that is computable in O(1)O(1) time then the number of R-chromatic triangles in G   can be computed in o(n2.687)o(n2.687) time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 25, March 2014, Pages 66–78
نویسندگان
, ,