On-line computation and maximum-weighted hereditary subgrah problems
Marc Demange, Bernard Kouakou, Éric Soutif · HAL - CNAM · 2011
In this paper1 we study the on-line version of maximum-weighted hereditarysubgraph problems. In our on-line model, the final instance (a graph with n vertices) isrevealed in t clusters, 2 ? t ? n . We first focus on an on-line version of the maximumweightedhereditary subgraph problem. Then, we deal with the particular case of theindependent set problem. We are interested in two types of results: the competitive ratioguaranteed by the on-line algorithm and hardness results that account for the difficulty ofthe problems and for the quality of algorithms developed to solve them.