کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4646548 1413648 2017 8 صفحه PDF سفارش دهید دانلود رایگان
عنوان انگلیسی مقاله ISI
Acyclicity in edge-colored graphs
ترجمه فارسی عنوان
غیرچرخه‌ای بودن در نمودارهای لبه رنگی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت
کلمات کلیدی
نمودار لبه رنگی ؛پیاده روی به درستی رنگی شده؛ پیاده روی بسته؛ دنباله بسته؛ غیرقابل چرخش
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A walk WW in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in WW is of different color. We introduce and study five types of PC acyclicity in edge-colored graphs such that graphs of PC acyclicity of type ii is a proper superset of graphs of acyclicity of type i+1i+1, i=1,2,3,4.i=1,2,3,4. The first three types are equivalent to the absence of PC cycles, PC closed trails, and PC closed walks, respectively. While graphs of types 1, 2 and 3 can be recognized in polynomial time, the problem of recognizing graphs of type 4 is, somewhat surprisingly, NP-hard even for 2-edge-colored graphs (i.e., when only two colors are used). The same problem with respect to type 5 is polynomial-time solvable for all edge-colored graphs. Using the five types, we investigate the border between intractability and tractability for the problems of finding the maximum number of internally vertex-disjoint PC paths between two vertices and the minimum number of vertices to meet all PC paths between two vertices.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 2, 6 February 2017, Pages 1–8
نویسندگان
, , , , ,
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت