کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414332 | 680890 | 2008 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Triangulations without pointed spanning trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Problem 50 in the Open Problems Project of the computational geometry community asks whether any triangulation on a point set in the plane contains a pointed spanning tree as a subgraph. We provide a counterexample. As a consequence we show that there exist triangulations which require a linear number of edge flips to become Hamiltonian.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 40, Issue 1, May 2008, Pages 79-83
Journal: Computational Geometry - Volume 40, Issue 1, May 2008, Pages 79-83