کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872263 | 681647 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the tree-depth of random graphs
ترجمه فارسی عنوان
در عمق درخت نمودار تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
درخت عمق، درخت عرض، نمودار تصادفی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Tree-depth is a parameter introduced under several names as a measure of sparsity of a graph. We compute asymptotic values of the tree-depth of a random graph on n vertices where each edge appears independently with probability p. For dense graphs, npâ+â, the tree-depth of a random graph G is aastd(G)=nâO(n/p). Random graphs with p=c/n, have aaslinear tree-depth when c>1, the tree-depth is Î(logn) when c=1 and Î(loglogn) for c<1. The result for c>1 is derived from the computation of tree-width and provides a more direct proof of a conjecture by Gao on the linearity of tree-width recently proved by Lee, Lee and Oum (2012) [15]. We also show that, for c=1, every width parameter is aasconstant, and that random regular graphs have linear tree-depth.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 168, 11 May 2014, Pages 119-126
Journal: Discrete Applied Mathematics - Volume 168, 11 May 2014, Pages 119-126
نویسندگان
G. Perarnau, O. Serra,