کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1142342 957143 2013 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Tree-compositions and orientations
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Tree-compositions and orientations
چکیده انگلیسی

A tree-composition is a tree-like family that serves to describe the obstacles to kk-edge-connected orientability of mixed graphs. Here we derive a structural result on tree-compositions that gives rise to a simple algorithm for computing an obstacle when the orientation does not exist.As another application, we show a min–max theorem on the minimal in-degree of a given node set in a kk-edge-connected orientation of an undirected graph. This min–max formula can be simplified in the special case of k=1k=1.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 41, Issue 4, July 2013, Pages 336–342
نویسندگان
, ,