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