کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874202 | 1441028 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Are unique subgraphs not easier to find?
ترجمه فارسی عنوان
آیا زیرگرافی منحصر به فرد برای پیدا کردن آسان نیست؟
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Consider a pattern graph H with l edges, and a host graph G which may contain several occurrences of H. In [15], we claimed that the time complexity of the problems of finding an occurrence of H (if any) in G as well as that of the decision version of the problem are within a multiplicative factor OË(l3) of the time complexity for the corresponding problem, where the host graph is guaranteed to contain at most one occurrence of a subgraph isomorphic to H, and the notation OË() suppresses polylogarithmic in n factors. We show a counterexample to this too strong claim and correct it by providing an OË((l(dâ1)+2)l) bound on the multiplicative factor instead, where d is the maximum number of occurrences of H that can share the same edge in the input host graph. We provide also an analogous correction in the induced case when occurrences of induced subgraphs isomorphic to H are sought.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 134, June 2018, Pages 57-61
Journal: Information Processing Letters - Volume 134, June 2018, Pages 57-61
نویسندگان
MirosÅaw Kowaluk, Andrzej Lingas,