کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332156 | 687156 | 2005 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Note on the Homogeneous Set Sandwich Problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A homogeneous set is a non-trivial module of a graph, i.e., a non-unitary, proper subset H of a graph's vertices such that all vertices in H have the same neighbors outside H. Given two graphs G1(V,E1), G2(V,E2), the Homogeneous Set Sandwich Problem asks whether there exists a sandwich graph GS(V,ES), E1âESâE2, which has a homogeneous set. Recently, Tang et al. [Inform. Process. Lett. 77 (2001) 17-22] proposed an interesting O(âµ1â
n2) algorithm for this problem, which has been considered its most efficient algorithm since. We show the incorrectness of their algorithm by presenting three counterexamples.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 93, Issue 2, 31 January 2005, Pages 75-81
Journal: Information Processing Letters - Volume 93, Issue 2, 31 January 2005, Pages 75-81
نویسندگان
Celina M.H. de Figueiredo, VinÃcius G.P. de Sá,