Article ID: | iaor20062220 |
Country: | Netherlands |
Volume: | 165 |
Issue: | 2 |
Start Page Number: | 387 |
End Page Number: | 397 |
Publication Date: | Sep 2005 |
Journal: | European Journal of Operational Research |
Authors: | Sevastianov S.V. |
Keywords: | scheduling, graphs, computational analysis |
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.