کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648010 | 1342388 | 2012 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Subgraph isomorphism in graph classes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We investigate the computational complexity of the following restricted variant of Subgraph Isomorphism: given a pair of connected graphs G=(VG,EG)G=(VG,EG) and H=(VH,EH)H=(VH,EH), determine if HH is isomorphic to a spanning subgraph of GG. The problem is NP-complete in general, and thus we consider cases where GG and HH belong to the same graph class such as the class of proper interval graphs, of trivially perfect graphs, and of bipartite permutation graphs. For these graph classes, several restricted versions of Subgraph Isomorphism such as Hamiltonian Path, Clique, Bandwidth, and Graph Isomorphism can be solved in polynomial time, while these problems are hard in general.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 21, 6 November 2012, Pages 3164–3173
Journal: Discrete Mathematics - Volume 312, Issue 21, 6 November 2012, Pages 3164–3173
نویسندگان
Shuji Kijima, Yota Otachi, Toshiki Saitoh, Takeaki Uno,