Abstract
The parameterized computational complexity of a collection of well-known problems including: BANDWIDTH, PRECEDENCE CONSTRAINED MULTIPROCESSOR SCHEDULING, LONGEST COMMON SUBSEQUENCE, DNA PHYSICAL MAPPING (or INTERVALIZING COLORED GRAPHS), PERFECT PHYLOGENY (or TRIANGULATING COLORED GRAPHS), COLORED CUTWIDTH, and FEASIBLE REGISTER ASSIGNMENT is explored. It is shown that these problems are hard for various levels of the W hierarchy. In the case of PRECEDENCE CONSTRAINED MULTIPROCESSOR SCHEDULING the results can be interpreted as providing substantial new complexity lower bounds on the outcome of [OPEN 8] of the Garey and Johnson list.
| Original language | English |
|---|---|
| Title of host publication | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |
| Place of Publication | New York, NY, United States |
| Publisher | Association for Computing Machinery |
| Pages | 449-458 |
| Number of pages | 10 |
| ISBN (Print) | 0897916638 |
| Publication status | Published - 1 Jan 1994 |
| Event | Proceedings of the 26th Annual ACM Symposium on the Theory of Computing - Montreal, Que, Can, United Kingdom Duration: 23 May 1994 → 25 May 1994 |
Conference
| Conference | Proceedings of the 26th Annual ACM Symposium on the Theory of Computing |
|---|---|
| Country/Territory | United Kingdom |
| City | Montreal, Que, Can |
| Period | 23/05/94 → 25/05/94 |