# [DKS05] On-line computation and maximum-weighted hereditary

**Conférence Internationale avec comité de lecture : **
ISAAC'05, 16th Annual Int. Symp. on Algorithms and Computation, Sanya, Hainan, China,
January 2005,

**motcle: **

**Résumé: **
In this paper, we study the on-line version of maximum-weighted
hereditary subgraph problems. In our on-line model, the final
instance-graph (which has n vertices) is revealed in t
clusters, 2 <= t <= n. We first focus on the on-line version
of the following problem: finding a maximum-weighted subgraph
satisfying some hereditary property. Then, we deal with the
particular case of the independent set. For all these problems, we
are interested in two types of results: the competitivity ratio
guaranteed by the on-line algorithm and hardness results that
account for the difficulty of the problems and for the quality of
algorithms developed to solve them.

Collaboration: