On-line vertex-covering

被引：18

作者：

Demange, M

Paschos, VT

机构：

[1] Univ Paris 09, CNRS, UMR 7024, LAMSADE, F-75775 Paris, France

[2] Univ Paris 01, CERMSEM, F-75231 Paris, France

[3] ESSEC, Dept DIS, F-95021 Cergy Pontoise, France

来源：

THEORETICAL COMPUTER SCIENCE | 2005年 / 332卷 / 1-3期

关键词：

on-line algorithm; competitive ratio; approximation; graph; vertex-covering;

D O I：

10.1016/j.tcs.2004.08.015

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We 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. (c) 2004 Elsevier B.V. All rights reserved.

引用

页码：83 / 108

页数：26