کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419283 | 683773 | 2015 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computing maximum non-crossing matching in convex bipartite graphs
ترجمه فارسی عنوان
محاسبه حداکثر تطابق عدم تطابق در گرافهای دو طرفه محدب
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
حداکثر تطبیق عدم عبور، حداکثر تطبیق نمودار دو طرفه محدب، الگوریتم ها، ساختارهای داده
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider computing a maximum non-crossing matching in convex bipartite graphs. For a convex bipartite graph of nn vertices and mm edges, we present an O(nlogn)O(nlogn) time algorithm for finding a maximum non-crossing matching in the graph. The previous best algorithm takes O(m+nlogn)O(m+nlogn) time (Malucelli et al., 1993). Since m=Θ(n2)m=Θ(n2) in the worst case, our result improves the previous work.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 187, 31 May 2015, Pages 50–60
Journal: Discrete Applied Mathematics - Volume 187, 31 May 2015, Pages 50–60
نویسندگان
Danny Z. Chen, Xiaomin Liu, Haitao Wang,