Show simple item record

dc.contributor.authorDemange, Marc
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2009-12-10T09:54:24Z
dc.date.available2009-12-10T09:54:24Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2651
dc.language.isoenen
dc.subjectGraphen
dc.subjectVertex-coveringen
dc.subjectCompetitive ratioen
dc.subjectOn-line algorithmen
dc.subject.ddc519en
dc.titleOn-line vertex-coveringen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherESSEC;France
dc.contributor.editoruniversityotherCERMSEM, Université Paris I;France
dc.description.abstractenWe study the minimum vertex-covering problem under two on-line models corresponding to two different ways vertices are revealed. The former one implies that the input-graph is revealed vertex- by-vertex. The second model implies that the input-graph is revealed per clusters, i.e. per induced subgraphs of the final graph. Under the cluster-model, we then relax the constraint that the choice of the part of the final solution dealing with each cluster has to be irrevocable, by allowing backtracking. We assume that one can change decisions upon a vertex membership of the final solution, this change implying, however, some cost depending on the number of the vertices changed.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol332en
dc.relation.isversionofjnlissue1-3en
dc.relation.isversionofjnldate2005
dc.relation.isversionofjnlpages83-108en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.tcs.2004.08.015en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProbabilités et mathématiques appliquéesen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record