On-line computation and maximum-weighted hereditary subgraph problems

In this paper, we study the on-line version of maximum-weighted hereditary subgraph problems. In our on-line model, the final instance-graph (which has n vertices) is revealed in t clusters, 2 ≤ t ≤ n. We first focus on the on-line version of the following problem : finding a maximum-weighted subgraph satisfying some hereditary property. Then, we deal with the particular case of the independent set. For all these problems, we are interested in two types of results : the competitivity ratio guaranteed by the on-line algorithm and hardness results that account for the difficulty of the problems and for the quality of algorithms developed to solve them.