کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438572 690295 2006 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Graph bandwidth of weighted caterpillars
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Graph bandwidth of weighted caterpillars
چکیده انگلیسی

Graph bandwidth minimization (GBM) is a classical and challenging problem in graph algorithms and combinatorial optimization. Most of existing researches on this problem have focused on unweighted graphs. In this paper, we study the bandwidth minimization problem of weighted caterpillars, and propose several algorithms for solving various types of caterpillars and general graphs. More specifically, we show that the GBM problem on caterpillars with hair-length at most 2 and the GBM problem on star-shape caterpillars are NP-complete, and give a lower bound of the graph bandwidth for general weighted graphs. For caterpillars with hair-length at most 1, we present an O(nlognlog(nwmax))-time algorithm to compute an optimal bandwidth layout, where n is the total number of vertices in the graph and wmax is the maximum wedge weight. For caterpillars with hair-length at most k, we give a k-approximation algorithm. For arbitrary caterpillars and general graphs, we give a heuristic algorithm and some experimental results. Experiments show that the solutions obtained by our heuristic algorithm are roughly within a factor of clog(n) of the lower bound for a small number c, which is consistent with the inapproximability results of this problem (i.e., no constant approximation for the GBM problem unless P=NP).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 363, Issue 3, 31 October 2006, Pages 266-277