On-line maximum-order induced hereditary subgraph problems |
| |
Authors: | Marc Demange Xavier Paradon Vangelis Th Paschos |
| |
Affiliation: | Department of Decision and Information Systems, ESSEC, France ; LAMSADE, UniversitéParis-Dauphine and CNRS UMR 7024 Place du Maréchal De Lattre de Tassigny, 75775 Paris Cedex 16, France ; |
| |
Abstract: | We first study the competitive ratio for the on‐line version of the problem of finding a maximum‐order induced subgraph satisfying some hereditary property, under the hypothesis that the input graph is revealed by clusters. Next, we focus ourselves on two of the most known instantiations of this problem: the maximum independent set and the maximum clique. Finally, we study a variant of the on‐line maximum‐weight induced hereditary subgraph problem. Our results can also be seen as general reductions, either from off‐line problems to the corresponding on‐line versions, or between on‐line problems. The concept of reduction was absent, until now, from the on‐line computation. |
| |
Keywords: | on-line algorithm hereditary property independent set clique reduction |
|
|