کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903645 | 1632749 | 2018 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On maximum common subgraph problems in series-parallel graphs
ترجمه فارسی عنوان
در حداکثر مشکلات متداول زیر گراف در نمودارهای سریال موازی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The complexity of the maximum common connected subgraph problem in partial k-trees is still not fully understood. Polynomial-time solutions are known for degree-bounded outerplanar graphs, a subclass of the partial 2-trees. On the other hand, the problem is known to be NP-hard in vertex-labeled partial 11-trees of bounded degree. We consider series-parallel graphs, i.e., partial 2-trees. We show that the problem remains NP-hard in biconnected series-parallel graphs with all but one vertex of degree 3 or less. A positive complexity result is presented for a related problem of high practical relevance which asks for a maximum common connected subgraph that preserves blocks and bridges of the input graphs. We present a polynomial time algorithm for this problem in series-parallel graphs, which utilizes a combination of BC- and SP-tree data structures to decompose both graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 68, February 2018, Pages 79-95
Journal: European Journal of Combinatorics - Volume 68, February 2018, Pages 79-95
نویسندگان
Nils Kriege, Florian Kurpicz, Petra Mutzel,