کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951286 | 1364339 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory](/preview/png/4951286.png)
چکیده انگلیسی
The three-way table problem is to decide if there exists an lÃmÃn table satisfying given line sums, and find a table if yes. Recently, it was shown to be fixed-parameter tractable with parameters l,m. Here we extend this and show that the huge version of the problem, where the variable side n is encoded in binary, is also fixed-parameter tractable with parameters l,m. We also conclude that the huge multicommodity flow problem with a huge number of consumers is fixed-parameter tractable. One of our tools is a theorem about unimodular monoids which is of interest on its own right.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 83, Issue 1, February 2017, Pages 207-214
Journal: Journal of Computer and System Sciences - Volume 83, Issue 1, February 2017, Pages 207-214
نویسندگان
Shmuel Onn,