On-line Maximum-order Induced Hereditary Subgraph Problems

M. Demange, X. Paradon and V.T. Paschos

Papiers d'Economie Mathématique et Applications from Université Panthéon-Sorbonne (Paris 1)

Abstract: We first study the competitivity 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.

Keywords: COMPETITION; HEREDITY; HEREDITARY PROPERTY (search for similar items in EconPapers)
JEL-codes: C60 C61 C69 (search for similar items in EconPapers)
Pages: 13 pages
Date: 2000
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:fth:pariem:2000.114

Access Statistics for this paper

More papers in Papiers d'Economie Mathématique et Applications from Université Panthéon-Sorbonne (Paris 1) France; Universite de Paris I - Pantheon- Sorbonne, 12 Place de Pantheon-75005 Paris, France. Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().