کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334269 | 690355 | 2005 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Graphical condensation of plane graphs: A combinatorial approach
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The method of graphical vertex-condensation for enumerating perfect matchings of plane bipartite graph was found by Propp [Generalized Domino-shuffling, Theoret. Comput. Sci. 303 (2003) 267-301], and was generalized by Kuo [Applications of graphical condensation for enumerating matchings and tilings, Theoret. Comput. Sci. 319 (2004) 29-57] and Yan and Zhang [Graphical condensation for enumerating perfect matchings, J. Combin. Theory Ser. A 110 (2005) 113-125]. In this paper, by a purely combinatorial method some explicit identities on graphical vertex-condensation for enumerating perfect matchings of plane graphs (which do not need to be bipartite) are obtained. As applications of our results, some results on graphical edge-condensation for enumerating perfect matchings are proved, and we count the sum of weights of perfect matchings of weighted Aztec diamond.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 349, Issue 3, 16 December 2005, Pages 452-461
Journal: Theoretical Computer Science - Volume 349, Issue 3, 16 December 2005, Pages 452-461
نویسندگان
Weigen Yan, Yeong-Nan Yeh, Fuji Zhang,