کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418502 681678 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complexity aspects of the triangle path convexity
ترجمه فارسی عنوان
جنبه های پیچیدگی تحدب مسیر مثلث
کلمات کلیدی
تعداد تحدب؛ تحدب نمودار؛ شماره بدنه؛ تحدب مسیر مثلث
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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
نویسندگان
, ,