Show simple item record

dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-04-06T09:35:55Z
dc.date.available2010-04-06T09:35:55Z
dc.date.issued2001
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3835
dc.language.isoenen
dc.subjectIndependent seten
dc.subjectColoringen
dc.subjectApproximation algorithmen
dc.subjectOn-line computationen
dc.subject.ddc003en
dc.titleOn-line independent set by coloring verticesen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn 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.en
dc.relation.isversionofjnlnameOperational Research
dc.relation.isversionofjnlvol1en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2001-09
dc.relation.isversionofjnlpages213-224en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/BF02936352en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record