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: C69 C60 C61 (search for similar items in EconPapers)
Date: 2000

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: http://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)
Address: France; Universite de Paris I - Pantheon- Sorbonne, 12 Place de Pantheon-75005 Paris, France
Contact information at EDIRC.
Series data maintained by Thomas Krichel ().