کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333168 | 688607 | 2009 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An exact algorithm for subgraph homeomorphism
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An exact algorithm for subgraph homeomorphism An exact algorithm for subgraph homeomorphism](/preview/png/10333168.png)
چکیده انگلیسی
We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2nâpnO(1) or in time 3nâpnO(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the time complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 464-468
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 464-468
نویسندگان
Andrzej Lingas, Martin Wahlen,