کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871075 | 1440177 | 2018 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient enumeration of graph orientations with sources
ترجمه فارسی عنوان
شمارش کارآمد از جهت گیری گراف با منابع
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شمارش جهت گیری آسیکلیکی، جهت گیری های سیکلی، تاخیر انداختن،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An orientation of an undirected graph is obtained by assigning a direction to each of its edges. It is called cyclic when a directed cycle appears, and acyclic otherwise. We study efficient algorithms for enumerating the orientations of an undirected graph. To get the full picture, we consider both the cases of acyclic and cyclic orientations, under some rules specifying which nodes are the sources (i.e. their incident edges are all directed outwards). Our enumeration algorithms use linear space and provide new bounds for the delay, which is the maximum elapsed time between the output of any two consecutively listed solutions. We obtain a delay of O(m) for acyclic orientations and OÌ(m) for cyclic ones. When just a single source is specified, these delays become O(mâ
n) and O(mâ
h+h3), respectively, where h is the girth of the graph without the given source. When multiple sources are specified, the delays are the same as in the single source case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 246, 10 September 2018, Pages 22-37
Journal: Discrete Applied Mathematics - Volume 246, 10 September 2018, Pages 22-37
نویسندگان
Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi,