کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874147 1441025 2018 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Linkage on the infinite grid
ترجمه فارسی عنوان
پیوند در شبکه بی نهایت
کلمات کلیدی
شبکه های اتصال مشکلات ترکیبی شبکه بی نهایت، پیوند مسیر پذیری،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
For k fixed, a graph G is k-path-pairable, if for any set of k disjoint pairs of vertices, si,ti, 1≤i≤k, there exist pairwise edge-disjoint si,ti-paths in G. Bounds on path-pairability are given here if G is the graph of the infinite integer grid in the Euclidean plane (vertices of G are the points of integer coordinates and two vertices are adjacent if and only if their Manhattan distance is 1). We prove that G is 10-path-pairable and at most 14-path-pairable. Related results and conjectures are summarized also for the integer halfplane, for the positive integer quadrant and for finite grids.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 137, September 2018, Pages 51-56
نویسندگان
, , ,