الگوریتم های سریع تر برای یافتن و شمارش زیرگراف.
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|79032||2012||9 صفحه PDF||سفارش دهید||8488 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Journal of Computer and System Sciences, Volume 78, Issue 3, May 2012, Pages 698–706
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.