Algorithms in the W-Hierarchy |
| |
| Authors: | Jonathan F Buss Tarique Islam |
| |
| Affiliation: | (1) Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 |
| |
| Abstract: | We show new upper bounds for problems in the W-hierarchy of fixed-parameter complexity. A crucial ingredient of our proofs
is an extension to the W-RAM model, which permits more-powerful operations but remains equivalent to the original. We use
the extended model to give new upper bounds for Subsetsum, Maximum Irredundant Set, and various problems concerning intersection
of finite-state machines. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
