×

Reducing off-line to on-line: an example and its application. (English) Zbl 1054.68099

The author considers the problem of finding a maximum weight induced subgraph with a given hereditary property (e.g., a clique) in a graph with defined vertex weight. He discusses relations between off-line and on-line versions of the problem. In the latter case the instance is not supposed to be completely known before one begins to solve it, but it is revealed step-by-step.

MSC:

68R10 Graph theory (including graph drawing) in computer science
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI