کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871547 | 1440187 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Edge-intersection graphs of boundary-generated paths in a grid
ترجمه فارسی عنوان
نمودارهای لبه تقاطع مسیرهای تولید مرزی در یک شبکه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that âEPG graphs can be covered by two collections of vertex-disjoint co-bipartite chain graphs. This leads us to a linear-time testable characterization of âEPG trees and also an almost tight upper bound on the equivalence covering number of general âEPG graphs. We also study the cases of two-sided âEPG and three-sided âEPG graphs, which are respectively, the subclasses of âEPG graphs obtained when all the boundary-vertex pairs which generate the paths are restricted to lie on at most two or three boundaries of the grid. For the former case, we give a complete characterization.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 214-222
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 214-222
نویسندگان
Martin Charles Golumbic, Gila Morgenstern, Deepak Rajendraprasad,