Article ID: | iaor20072622 |
Country: | France |
Volume: | 40 |
Issue: | 2 |
Start Page Number: | 129 |
End Page Number: | 142 |
Publication Date: | Apr 2006 |
Journal: | RAIRO Operations Research |
Authors: | Paschos Vangelis Th., Escoffier Bruno |
In on-line computation, the instance of the problem dealt is not entirely known from the beginning of the solution process, but it is revealed step-by-step. In this paper we deal with on-line independent set. On-line models studied until now for this problem suppose that the input graph is initially empty and revealed either vertex-by-vertex, or cluster-by-cluster. Here we present a new on-line model quite different to the ones already studied. It assumes that a superset of the final graph is initially present (in our case the complete graph on the order