کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875616 | 1441976 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Cograph generation with linear delay
ترجمه فارسی عنوان
تولید عکس با تاخیر خطی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
عکسها، ترکیبی از شمارنده، الگوریتم های شمارشگر،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Cographs have always been a research target in areas such as coloring, graph decomposition, and spectral theory. In this work, we present an algorithm to generate all unlabeled cographs with n vertices, based on the generation of cotrees. The delay of our algorithm (time spent between two consecutive outputs) is O(n). The time needed to generate the first output is also O(n), which gives an overall O(nMn) time complexity, where Mn is the number of unlabeled cographs with n vertices. The algorithm avoids the generation of duplicates (isomorphic outputs) and produces, as a by-product, a linear ordering of unlabeled cographs with n vertices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 713, 22 February 2018, Pages 1-10
Journal: Theoretical Computer Science - Volume 713, 22 February 2018, Pages 1-10
نویسندگان
Átila A. Jones, Fábio Protti, Renata R. Del-Vecchio,