On-line models and algorithms for max independent set
Paschos, Vangelis; Escoffier, Bruno (2006), On-line models and algorithms for max independent set, RAIRO, 40, 2, p. 129-142. http://dx.doi.org/10.1051/ro:2006014
TypeArticle accepté pour publication ou publié
External document linkhttp://hal.archives-ouvertes.fr/hal-00017612/fr/
MetadataShow full item record
Abstract (EN)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 in [Demange, Paradon and Paschos, Lect. Notes Comput. Sci. 1963 (2000) 326-334] and study relaxations assuming that some paying backtracking is allowed.
Subjects / KeywordsApproximation algorithms; on-line algorithms; maximum independent set; competitive ratio
Showing items related by title and author.
Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié