کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646961 | 1342320 | 2015 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we design an algorithm that, given a directed graph GG and the Cartesian-product decomposition of its underlying undirected graph G̃, produces the directed Cartesian-product decomposition of GG in linear time. This is the first time that the linear complexity is achieved for this problem, which has two major consequences. Firstly, it shows that the directed and undirected versions of the Cartesian-product decomposition of graphs are linear-time equivalent problems. And secondly, as there already exists a linear-time algorithm for solving the undirected version of the problem, combined together, it provides the first linear-time algorithm for computing the directed Cartesian-product decomposition of a directed graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 12, 6 December 2015, Pages 2393–2407
Journal: Discrete Mathematics - Volume 338, Issue 12, 6 December 2015, Pages 2393–2407
نویسندگان
Christophe Crespelle, Eric Thierry,