کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
13430687 | 1842452 | 2019 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We give an algorithm that for an input planar graph G of n vertices and an integer k, in min{O(nlog3n),O(nk2)} time either constructs a branch-decomposition of G of width at most (2+δ)k, where δ>0 is a constant, or a (k+1)Ãk+12 cylinder minor of G implying bw(G)>k, where bw(G) is the branchwidth of G. This is the first OÌ(n) time constant-factor approximation for branchwidth/treewidth and largest grid/cylinder minors of planar graphs and improves the previous min{O(n1+ϵ),O(nk2)} (where ϵ>0 is a constant) time constant-factor approximations. For a planar graph G andk=bw(G), a branch-decomposition of width at most (2+δ)k
and a gÃg2 cylinder/grid minor with g=kβ, where β>2 is a constant, can be computed by our algorithm in min{O(nlog3nlogk),O(nk2logk)} time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 257, 31 March 2019, Pages 186-205
Journal: Discrete Applied Mathematics - Volume 257, 31 March 2019, Pages 186-205
نویسندگان
Qian-Ping Gu, Gengchun Xu,