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
TypeArticle accepté pour publication ou publié
Journal nameInternational Transactions in Operational Research
MetadataShow full item record
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 / KeywordsApproximation algorithms; On-line algorithms; Maximum independent set; Competitive ratio
Showing items related by title and author.