Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951286 | Journal of Computer and System Sciences | 2017 | 8 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Shmuel Onn,