کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430723 688133 2012 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Faster algorithms for finding and counting subgraphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Faster algorithms for finding and counting subgraphs
چکیده انگلیسی

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.


► We give algorithms for subgraph isomorphism.
► We define new multivariate Homomorphism Polynomial and construct compact an arithmetic circuit for this polynomial.
► The work extends and unifies most of the known results on sub-path and sub-tree isomorphisms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 78, Issue 3, May 2012, Pages 698–706
نویسندگان
, , , , ,