On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems

Marc Demange, Bernard Kouakou, Eric Soutif

In this paper we study the on-line version of maximum-weighted hereditary subgraph problems. In our on-line model, the final instance (a graph with $n$ vertices) is revealed in $t$ clusters, $2 \leq t \leq n$ . We first focus on an on-line version of the maximum- weighted hereditary subgraph problem. Then, we deal with the particular case of the independent set problem. We are interested in two types of results: the competitive 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.