کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431725 | 688618 | 2007 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we deal with the maximum integer multiflow and the minimum multicut problems in rectilinear grid graphs with uniform capacities on the edges. The first problem is known to be NPNP-hard when any vertex can be a terminal, and we show that the second one is also NPNP-hard. Then, we study the case where the terminals are located in a two-sided way on the boundary of the outer face. We prove that, in this case, both problems are polynomial-time solvable. Furthermore, we give two efficient combinatorial algorithms using a primal-dual approach. Our work is based on previous results concerning related decision problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 5, Issue 1, March 2007, Pages 36–54
Journal: Journal of Discrete Algorithms - Volume 5, Issue 1, March 2007, Pages 36–54
نویسندگان
Cédric Bentz, Marie-Christine Costa, Frédéric Roupin,