کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420743 | 683976 | 2006 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fully dynamic recognition algorithm and certificate for directed cographs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
This paper presents an optimal fully dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G , the algorithm supports arc and vertex modification (insertion or deletion) in O(d)O(d) time where d is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular decomposition tree is updated; otherwise, a certificate is returned within the same complexity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 12, 15 July 2006, Pages 1722–1741
Journal: Discrete Applied Mathematics - Volume 154, Issue 12, 15 July 2006, Pages 1722–1741
نویسندگان
C. Crespelle, C. Paul,