On-line computation and maximum-weighted hereditary subgraph problems

Marc Demange (), Bernard Kouakou () and Eric Soutif ()
Additional contact information
Marc Demange: ESSEC, SID department
Bernard Kouakou: Centre d'Economie de la Sorbonne
Eric Soutif: CEDRIC, CNAM

Cahiers de la Maison des Sciences Economiques from Université Panthéon-Sorbonne (Paris 1)

Abstract: In this paper, we study the on-line version of maximum-weighted hereditary subgraph problems. In our on-line model, the final instance-graph (which has n vertices) is revealed in t clusters, 2 £ t £ n. We first focus on the on-line version of the following problem: finding a maximum-weighted subgraph satisfying some hereditary property. Then, we deal with the particular case of the independent set. For all these problems, we are interested in two types of results: the competitivity ratio guaranteed by the on-line algorithm and hardness results that account for the difficulty of the problems and for the quality of algorithms developed to solve them

Keywords: On-line algorithm; hereditary property; independent set; competitivity ratio (search for similar items in EconPapers)
Pages: 11 pages
Date: 2006-05
References: View complete reference list from CitEc
Citations:

Published in International Symposium on Algorithms and Computation, ISAAC 2005: Algorithms and Computation pp 433-442

Downloads: (external link)
https://hal.archives-ouvertes.fr/halshs-00115615 (application/pdf)
https://doi.org/10.1007/11602613_44

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:mse:wpsorb:v06034

Access Statistics for this paper

More papers in Cahiers de la Maison des Sciences Economiques from Université Panthéon-Sorbonne (Paris 1) Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().