کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141443 1489502 2014 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Orientations and detachments of graphs with prescribed degrees and connectivity
ترجمه فارسی عنوان
جهت گیری ها و جدایی از نمودار ها با درجه های مجاز و اتصال
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
چکیده انگلیسی
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
نویسندگان
, ,