کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434468 | 689740 | 2014 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
(Nearly-)tight bounds on the contiguity and linearity of cographs
ترجمه فارسی عنوان
(تقریبا) محدوده های تنگ در همبستگی و خطی بودن تصاویر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بستگی دارد، خطی بودن، عکسها، رمزگذاری گراف
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper we show that the contiguity and linearity of cographs on n vertices are both O(logn). Moreover, we show that this bound is tight for contiguity as there exists a family of cographs on n vertices whose contiguity is Ω(logn). We also provide an Ω(logn/loglogn) lower bound on the maximum linearity of cographs on n vertices. As a by-product of our proofs, we obtain a min–max theorem, which is worth of interest in itself, stating equality between the rank of a tree and the minimum height of one of its path partitions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 522, 20 February 2014, Pages 1–12
Journal: Theoretical Computer Science - Volume 522, 20 February 2014, Pages 1–12
نویسندگان
Christophe Crespelle, Philippe Gambette,