کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431005 | 688249 | 2012 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The astral index of a graph is defined as the smallest number of astral graphs (also known as threshold graphs) into which the graph can be decomposed, divided by the number of vertices in the graph. The astral index is a promising new graph measure for analysing the structure of graphs in applications. In this paper, we prove some theoretical results concerning astral graphs and the astral index. We reveal a connection between astral graphs and scale-free graphs. We prove that finding the exact value of the astral index is an NP-complete problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 12, April 2012, Pages 24–28
Journal: Journal of Discrete Algorithms - Volume 12, April 2012, Pages 24–28
نویسندگان
Alexei Vernitski, Artem Pyatkin,