On-line independent set by coloring vertices
Paschos, Vangelis (2001), On-line independent set by coloring vertices, Operational Research, 1, 3, p. 213-224. http://dx.doi.org/10.1007/BF02936352
Type
Article accepté pour publication ou publiéDate
2001Journal name
Operational ResearchVolume
1Number
3Publisher
Springer
Pages
213-224
Publication identifier
Metadata
Show full item recordAuthor(s)
Paschos, VangelisAbstract (EN)
In on-line computation, the instance of a problem is revealed step-by-step and one has, at the end of each step, to irrevocably decide on the part of the final solution dealing with this step. In this paper, we study the on-line independent set under a model assuming that the input graph G is revealed by non-empty clusters, i.e., by induced subgraphs of G. We suppose that the order of the graph, as well as the number of clusters needed so that the whole of the graph is revealed are a priori known. The algorithm we propose implies approximation of the vertex-coloring problem in each cluster. We first establish a general result for the competitivity of the method studied. Next, we restrict ourselves in natural and well-known independent set sub-problems and perform a precise evaluation of the competitivity ratio of our algorithm for the sub-problems considered.Subjects / Keywords
Independent set; Coloring; Approximation algorithm; On-line computationRelated items
Showing items related by title and author.
-
Paschos, Vangelis; Veslot, Hélène (2001) Communication / Conférence
-
Paschos, Vangelis; Escoffier, Bruno (2006) Article accepté pour publication ou publié
-
Demange, Marc; Paschos, Vangelis (1995) Communication / Conférence
-
Bourgeois, Nicolas; Ausiello, Giorgio; Paschos, Vangelis; Giannakos, Aristotelis (2009) Article accepté pour publication ou publié
-
Ausiello, Giorgio; Giannakos, Aristotelis; Paschos, Vangelis (2006) Communication / Conférence