%0 Journal Article
%T On-line computation and maximum-weighted hereditary subgraph problems
%A Demange Marc
%A Kouakou Bernard
%A Soutif Eric
%J Yugoslav Journal of Operations Research
%D 2011
%I University of Belgrade
%R 10.2298/yjor1101011d
%X In this paper1 we study the on-line version of maximum-weighted hereditary subgraph problems. In our on-line model, the final instance (a graph with n vertices) is revealed in t clusters, 2 ¡Ü t ¡Ü n . We first focus on an on-line version of the maximumweighted hereditary subgraph problem. Then, we deal with the particular case of the independent set problem. We are interested in two types of results: the competitive 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.
%K On-line algorithms
%K hereditary property
%K independent set
%K competitive ratio
%U http://www.doiserbia.nb.rs/img/doi/0354-0243/2011/0354-02431101011D.pdf