کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874147 | 1441025 | 2018 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Linkage on the infinite grid
ترجمه فارسی عنوان
پیوند در شبکه بی نهایت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شبکه های اتصال مشکلات ترکیبی شبکه بی نهایت، پیوند مسیر پذیری،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Information Processing Letters - Volume 137, September 2018, Pages 51-56
نویسندگان
Adam S. Jobson, André E. Kézdy, JenÅ Lehel,