کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4636753 | 1340727 | 2006 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A similarity measure for graphs with low computational complexity
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We present and analyze an algorithm to measure the structural similarity of generalized trees, a new graph class which includes rooted trees. For this, we represent structural properties of graphs as strings and define the similarity of two graphs as optimal alignments of the corresponding property stings. We prove that the obtained graph similarity measures are so called Backward similarity measures. From this we find that the time complexity of our algorithm is polynomial and, hence, significantly better than the time complexity of classical graph similarity methods based on isomorphic relations.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 182, Issue 1, 1 November 2006, Pages 447–459
Journal: Applied Mathematics and Computation - Volume 182, Issue 1, 1 November 2006, Pages 447–459
نویسندگان
Matthias Dehmer, Frank Emmert-Streib, Jürgen Kilian,