کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871461 | 1440186 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The convexity of induced paths of order three and applications: Complexity aspects
ترجمه فارسی عنوان
محدب مسیرهای القا شده سه مرتبه و برنامه های کاربردی: جنبه های پیچیدگی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we introduce a new convexity on graphs similar to the well known P3-convexity, which we will call P3â-convexity. We show that several P3â-convexity parameters (hull number, convexity number, Carathéodory number, Radon number, interval number and percolation time) are NP-hard even on bipartite graphs. We prove a strong relationship between this convexity and the well known geodesic convexity, which implies several NP-hardness results for the latter. In order to show that, we prove that the hull number for the P3-convexity is NP-hard even for subgraphs of grids and that the convexity number for the P3-convexity is NP-hard even for bipartite graphs with diameter 3. We also obtain linear time algorithms to determine those parameters for the above mentioned convexities for cographs and P4-sparse graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 237, 11 March 2018, Pages 33-42
Journal: Discrete Applied Mathematics - Volume 237, 11 March 2018, Pages 33-42
نویسندگان
Rafael T. Araújo, Rudini M. Sampaio, VinÃcius F. dos Santos, Jayme L. Szwarcfiter,