On-line Maximum-order Induced Hereditary Subgraph Problems.

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.

MoreLess

Year of publication:	2000
Authors:	Demange, M. ; Paradon, X. ; Paschos, V.T.
Institutions:	Centre de recherche de mathématiques et économie mathématique (CERMSEM), Centre d'Économie de la Sorbonne
Subject:	COMPETITION \| HEREDITY \| HEREDITARY PROPERTY

More details

Series:	Papiers d'Economie Mathématique et Applications.
Type of publication:	Book / Working Paper
Notes:	13 pages
Classification:	C69 - Mathematical Methods and Programming. Other ; C60 - Mathematical Methods and Programming. General ; C61 - Optimization Techniques; Programming Models; Dynamic Analysis
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005478370