کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418502 | 681678 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity aspects of the triangle path convexity
ترجمه فارسی عنوان
جنبه های پیچیدگی تحدب مسیر مثلث
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تعداد تحدب؛ تحدب نمودار؛ شماره بدنه؛ تحدب مسیر مثلث
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In a triangle path v1,…,vtv1,…,vt of a graph GG no edges exist joining vertices vivi and vjvj such that |j−i|>2|j−i|>2. A set S⊆V(G)S⊆V(G) is convex in the triangle path convexity of GG, or tt-convex , if the vertices of every triangle path joining two vertices of SS are in SS. The cardinality of a maximum proper tt-convex subset of V(G)V(G) is the tt-convexity number of GG and the cardinality of a minimum set of vertices whose tt-convex hull is V(G)V(G) is the tt-hull number of GG. We solve the fundamental complexity problems on the triangle path convexity. Among them, we present polynomial-time algorithms for determining the tt-convexity number and the tt-hull number of a general graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 206, 19 June 2016, Pages 39–47
Journal: Discrete Applied Mathematics - Volume 206, 19 June 2016, Pages 39–47
نویسندگان
Mitre C. Dourado, Rudini M. Sampaio,