کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652736 | 1632595 | 2010 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Estimating the relevance on Communication Lines Based on the Number of Edge Covers
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Counting the number of edge covers on graphs, denoted as the #Edge_Covers problem, is a #P-complete problem. Knowing the number of edge covers is useful for estimating the relevance of the lines in a communication network, which is an important measure in the reliability analysis of a network. In this paper, we present efficient algorithms for solving the #Edge_Covers problem on the most common network topologies, namely, Bus, Stars, Trees and Rings. We show that if the topology of the network G does not contain intersecting cycles (any pair of cycles with common edges), then the number of edge covers can be computed in linear time on the size of G.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 36, 1 August 2010, Pages 247-254
Journal: Electronic Notes in Discrete Mathematics - Volume 36, 1 August 2010, Pages 247-254