On-line models and algorithms for max independent set

On-line models and algorithms for max independent set

0.00 Avg rating0 Votes
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: ,
Abstract:

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 n of the final graph) and edges are progressively removed until the achievement of the final graph. Next, we revisit the model introduced by Demange, Paradon and Paschos, and study relaxations assuming that some paying backtracking is allowed.

Reviews

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