کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | ترجمه فارسی | نسخه تمام متن |
---|---|---|---|---|---|
6875674 | 1441979 | 2018 | 9 صفحه PDF | سفارش دهید | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Constructing an indeterminate string from its associated graph
ترجمه فارسی عنوان
ساخت یک رشته نامشخص از نمودار مرتبط آن
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت
کلمات کلیدی
الگوریتم های رشته، رشته های نامرئی، کلایک، برچسب گذاری نمودار،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
As discussed at length in Christodoulakis et al. (2015) [3], there is a natural one-many correspondence between simple undirected graphs G with vertex set V={1,2,â¦,n} and indeterminate stringsx=x[1..n] - that is, sequences of subsets of some alphabet Σ. In this paper, given G, we consider the “reverse engineering” problem of computing a corresponding x on an alphabet Σmin of minimum cardinality. This turns out to be equivalent to the NP-hard problem of computing the intersection number of G, thus in turn equivalent to the clique cover problem. We describe a heuristic algorithm that computes an approximation to Σmin and a corresponding x. We give various properties of our algorithm, including some experimental evidence that on average it requires O(n2logâ¡n) time. We compare it with other heuristics, and state some conjectures and open problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 710, 1 February 2018, Pages 88-96
Journal: Theoretical Computer Science - Volume 710, 1 February 2018, Pages 88-96
نویسندگان
Joel Helling, P.J. Ryan, W.F. Smyth, Michael Soltys,
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت