دانلود مقاله ISI انگلیسی شماره 79690
عنوان فارسی مقاله

برنامه نویسی پویا و planarity: الگوریتم ها بر اساس تجزیه درخت بهبود یافته ☆

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
79690 2010 9 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Dynamic programming and planarity: Improved tree-decomposition based algorithms ☆
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Discrete Applied Mathematics, Volume 158, Issue 7, 6 April 2010, Pages 800–808

کلمات کلیدی
درخت تجزیه؛ برنامه نویسی پویا؛ مجموعه غالب مسطح؛ چرخه هامیلتونی مسطح؛ گراف مسطح TSP؛ شاخه تجزیه
پیش نمایش مقاله
پیش نمایش مقاله برنامه نویسی پویا و planarity: الگوریتم ها بر اساس تجزیه درخت بهبود یافته ☆

چکیده انگلیسی

We study some structural properties for tree-decompositions of 2-connected planar graphs that we use to improve upon the runtime of tree-decomposition based dynamic programming approaches for several NP-hard planar graph problems. E.g., we derive the fastest algorithm for Planar Dominating Set of runtime 3tw⋅nO(1)3tw⋅nO(1), when we take the width twtw of a given tree-decomposition as the measure for the exponential worst case behavior. We also introduce a tree-decomposition based approach to solve non-local problems efficiently, such as Planar Hamiltonian Cycle in runtime 6tw⋅nO(1)6tw⋅nO(1). From any input tree-decomposition of a 2-connected planar graph, one computes in time O(nm)O(nm) a tree-decomposition with geometric properties, which decomposes the plane into disks, and where the graph separators form Jordan curves in the plane.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.