Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9663750 | European Journal of Operational Research | 2005 | 11 Pages |
Abstract
A notion of multi-parameter complexity analysis of a discrete problem as the determining of complexities of its subproblems over all possible combinations of constraints on key parameters is introduced, and a notion of a basis system of subproblems is defined. Basic theorems on the existence, uniqueness and finiteness of the basis system are established. As an illustration to this approach, some results on the 4-parameter complexity analysis of the open shop scheduling problem and of the connected list coloring problem are presented.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
S.V. Sevastianov,