کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419705 | 683851 | 2009 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of recognizing directed path families
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A Directed Path Family is a family of subsets of some finite ground set whose members can be realized as arc sets of simple directed paths in some directed graph. In this paper we show that recognizing whether a given family is a Directed Path family is an NP-Complete problem, even when all members in the family have at most two elements. If instead of a family of subsets, we are given a collection of words from some finite alphabet, then deciding whether there exists a directed graph GG such that each word in the language is the set of arcs of some path in GG, is a polynomial-time solvable problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 11, 6 June 2009, Pages 2525–2535
Journal: Discrete Applied Mathematics - Volume 157, Issue 11, 6 June 2009, Pages 2525–2535
نویسندگان
N. Apollonio, P.G. Franciosa,