کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438431 690271 2008 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The maximum edge-disjoint paths problem in complete graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The maximum edge-disjoint paths problem in complete graphs
چکیده انگلیسی

In this paper, we consider the undirected version of the well known maximum edge-disjoint paths problem, restricted to complete graphs. We propose an off-line 3.75-approximation algorithm and an on-line 6.47-approximation algorithm, improving the earlier 9-approximation algorithm proposed by Carmi, Erlebach, and Okamoto [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143–155]. Moreover, we show that for the general case, no on-line algorithm is better than a (2−ε)-approximation, for all ε>0. For the special case when the number of paths is within a linear factor of the number of vertices of the graph, it is established that the problem can be optimally solved in polynomial time by an off-line algorithm, but that no on-line algorithm is better than a (1.5−ε)-approximation. Finally, the proposed techniques are used to obtain off-line and on-line algorithms with a constant approximation ratio for the related problems of edge congestion routing and wavelength routing in complete graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 399, Issues 1–2, 3 June 2008, Pages 128-140