کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952319 | 1364440 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient computation of the characteristic polynomial of a threshold graph
ترجمه فارسی عنوان
محاسبه کارایی چند جمله ای مشخص گراف یک آستانه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های کارآمد، نمودار آستانه، چند جمله ای مشخصه،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An efficient algorithm is presented to compute the characteristic polynomial of a threshold graph. Threshold graphs were introduced by Chvátal and Hammer, as well as by Henderson and Zalcstein in 1977. A threshold graph is obtained from a one vertex graph by repeatedly adding either an isolated vertex or a dominating vertex, which is a vertex adjacent to all the other vertices. Threshold graphs are special kinds of cographs, which themselves are special kinds of graphs of clique-width 2. We obtain a running time of O(nlog2â¡n) for computing the characteristic polynomial, while the previously fastest algorithm ran in quadratic time. We improve the running time drastically in the case where there is a small number of alternations between 0's and 1's in the sequence defining a threshold graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 657, Part A, 2 January 2017, Pages 3-10
Journal: Theoretical Computer Science - Volume 657, Part A, 2 January 2017, Pages 3-10
نویسندگان
Martin Fürer,