کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419311 683778 2015 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Many-to-many two-disjoint path covers in cylindrical and toroidal grids
ترجمه فارسی عنوان
بسیاری از مسیرهای دو طرفه در شبکههای استوانه ای و توربولزی پوشش می یابند
کلمات کلیدی
مسیر متقابل، پوشش مسیر پارتیشن مسیر، شبکه مربع، نمودار غلطکی شبکه استوانه ای
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

A many-to-many kk-disjoint path cover of a graph joining two disjoint vertex sets SS and TT of equal size kk is a set of kk vertex-disjoint paths between SS and TT that altogether cover every vertex of the graph. The many-to-many kk-disjoint path cover is classified as paired if each source in SS is further required to be paired with a specific sink in TT, or unpaired otherwise. In this paper, we first establish a necessary and sufficient condition for a bipartite cylindrical grid to have a paired many-to-many 22-disjoint path cover joining SS and TT. Based on this characterization, we then prove that, provided the set S∪TS∪T contains the equal numbers of vertices from different parts of the bipartition, the bipartite cylindrical grid always has an unpaired many-to-many 22-disjoint path cover. Additionally, we show that such balanced vertex sets also guarantee the existence of a paired many-to-many 22-disjoint path cover for any bipartite toroidal grid even if an arbitrary edge is removed.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 185, 20 April 2015, Pages 168–191
نویسندگان
, ,