کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141443 | 1489502 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Orientations and detachments of graphs with prescribed degrees and connectivity
ترجمه فارسی عنوان
جهت گیری ها و جدایی از نمودار ها با درجه های مجاز و اتصال
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کناره گیری، نمودار، گرایش، اربرسنس، درخت پوشا،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
چکیده انگلیسی
We give a necessary and sufficient condition for a graph to have an orientation that has k edge-disjoint arborescences rooted at a designated vertex s subject to lower and upper bounds on the in-degree at each vertex. The result is used to derive a characterization of graphs having a detachment that contains k edge-disjoint spanning trees. Efficient algorithms for finding those orientations and detachments are also described. In particular, the paper provides an algorithm for finding a connected (loopless) detachment in O(nm) time, improving on the previous best running time bound, where n and m denote the numbers of vertices and edges, respectively.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 12, May 2014, Pages 121-128
Journal: Discrete Optimization - Volume 12, May 2014, Pages 121-128
نویسندگان
Satoru Iwata, Tibor Jordán,