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

الگوریتم های سریع تر برای یافتن و شمارش زیرگراف.

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
79032 2012 9 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Faster algorithms for finding and counting subgraphs
منبع

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

Journal : Journal of Computer and System Sciences, Volume 78, Issue 3, May 2012, Pages 698–706

کلمات کلیدی
پیچیدگی پارامتر؛ زیرگراف ریختی - همریخت؛ شمارش ؛ Treewidth
پیش نمایش مقاله
پیش نمایش مقاله الگوریتم های سریع تر برای یافتن و شمارش زیرگراف.

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

In the Subgraph Isomorphism problem we are given two graphs F and G on k and n vertices respectively as an input, and the question is whether there exists a subgraph of G isomorphic to F. We show that if the treewidth of F is at most t, then there is a randomized algorithm for the Subgraph Isomorphism problem running in time O⁎(k2n2t)O⁎(2kn2t). Our proof is based on a novel construction of an arithmetic circuit of size at most nO(t)nO(t) for a new multivariate polynomial, Homomorphism Polynomial, of degree at most k, which in turn is used to solve the Subgraph Isomorphism problem. For the counting version of the Subgraph Isomorphism problem, where the objective is to count the number of distinct subgraphs of G that are isomorphic to F  , we give a deterministic algorithm running in time and space O⁎((nk/2)n2p) or (nk/2)nO(tlogk). We also give an algorithm running in time O⁎(2k(nk/2)n5p) and taking O⁎(np)O⁎(np) space. Here p and t denote the pathwidth and the treewidth of F, respectively. Our work improves on the previous results on Subgraph Isomorphism, it also extends and unifies most of the known results on sub-path and sub-tree isomorphisms.

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