Thumbnail

On-line maximum-order induced hereditary subgraph problems

Paschos, Vangelis; Demange, Marc; Paradon, Xavier (2005), On-line maximum-order induced hereditary subgraph problems, International Transactions in Operational Research, 12, 2, p. 185-201. http://dx.doi.org/10.1111/j.1475-3995.2005.00497.x

View/Open
Type
Article accepté pour publication ou publié
Date
2005
Journal name
International Transactions in Operational Research
Volume
12
Number
2
Publisher
Blackwell Publishing Limited
Pages
185-201
Publication identifier
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Demange, Marc
Paradon, Xavier
Abstract (EN)
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.
Subjects / Keywords
Approximation algorithms; On-line algorithms; Maximum independent set; Competitive ratio