کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431690 | 688613 | 2008 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fixed parameter algorithms for one-sided crossing minimization revisited
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We exhibit a small problem kernel for the one-sided crossing minimization problem. This problem plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover, we improve on the search tree algorithm developed in [V. Dujmović, S. Whitesides, An efficient fixed parameter tractable algorithm for 1-sided crossing minimization, Algorithmica 40 (2004) 15–31] and derive an O(k1.4656+kn2)O(1.4656k+kn2) algorithm for this problem, where k upperbounds the number of tolerated edge crossings in the drawings of an n-vertex graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 6, Issue 2, June 2008, Pages 313–323
Journal: Journal of Discrete Algorithms - Volume 6, Issue 2, June 2008, Pages 313–323
نویسندگان
Vida Dujmović, Henning Fernau, Michael Kaufmann,