On-line vertex-covering

Demange, Marc; Paschos, Vangelis

Demange, Marc; Paschos, Vangelis (2005), On-line vertex-covering, Theoretical Computer Science, 332, 1-3, p. 83-108. http://dx.doi.org/10.1016/j.tcs.2004.08.015

View/Open

publi128.pdf (444.1Kb)

Type

Article accepté pour publication ou publié

Date

2005

Journal name

Theoretical Computer Science

Volume

332

Number

1-3

Publisher

Elsevier

Pages

83-108

Abstract (EN)

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 ﬁnal graph. Under the cluster-model, we then relax the constraint that the choice of the part of the ﬁnal 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 ﬁnal solution, this change implying, however, some cost depending on the number of the vertices changed.

Subjects / Keywords

Graph; Vertex-covering; Competitive ratio; On-line algorithm