Premium
On‐line maximum‐order induced hereditary subgraph problems
Author(s) -
Demange Marc,
Paradon Xavier,
Paschos Vangelis Th.
Publication year - 2005
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
ISBN - 3-540-41348-0
DOI - 10.1111/j.1475-3995.2005.00497.x
Subject(s) - order (exchange) , line (geometry) , induced subgraph isomorphism problem , computer science , mathematics , combinatorics , business , graph , line graph , geometry , finance , voltage graph
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.