کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328496 | 684038 | 2005 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Embeddings of k-connected graphs of pathwidth k
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Embeddings of k-connected graphs of pathwidth k Embeddings of k-connected graphs of pathwidth k](/preview/png/10328496.png)
چکیده انگلیسی
We present O(n3) embedding algorithms (subgraph isomorphism and its generalizations) for classes of graphs of bounded pathwidth, where n is the number of vertices in the graph. These include the first polynomial-time algorithm for minor containment and the first O(nc) algorithm (c a constant independent of k) for topological embedding of graphs from subclasses of partial k-trees, as well as an O(n2) algorithm for subgraph isomorphism. Of independent interest are structural properties of k-connected graphs of bounded pathwidth on which our algorithms are based. We also describe special cases which reduce to various generalizations of string matching, permitting more efficient solutions. Finally, we describe nk+O(1) algorithms for solving these problems on arbitrary graphs of pathwidth at most k.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 145, Issue 2, 15 January 2005, Pages 242-265
Journal: Discrete Applied Mathematics - Volume 145, Issue 2, 15 January 2005, Pages 242-265
نویسندگان
Arvind Gupta, Naomi Nishimura, Andrzej Proskurowski, Prabhakar Ragde,