An introduction to multi-parameter complexity analysis of discrete problems

An introduction to multi-parameter complexity analysis of discrete problems

0.00 Avg rating0 Votes
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:
Keywords: scheduling, graphs, computational analysis
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.

Reviews

Required fields are marked *. Your email address will not be published.