کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651083 | 1632445 | 2007 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Pairs of trees in tree–tree triangulations
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A triangulation TT of a compact 2-manifold is said to be a tree–tree triangulation if the graph of TT can be partitioned into two induced trees. Hence each tree–tree triangulation is a triangulation of the 2-sphere. Recognizing tree–tree triangulations among all simple spherical ones can be seen to be an NP-complete problem. Some (exponentially many) pairs of trees into which graphs of some simple triangulations can be partitioned are characterized. In particular, for a pair made up of any tree and any long enough path, there is a spherical triangulation whose graph is partitionable into that pair.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 11–12, 28 May 2007, Pages 1499–1505
Journal: Discrete Mathematics - Volume 307, Issues 11–12, 28 May 2007, Pages 1499–1505
نویسندگان
Günter Schaar, Zdzisław Skupień,