On-line computation and maximum-weighted hereditary subgraph problems

Marc Demange (), Bernard Kouakou () and Eric Soutif ()
Additional contact information
Marc Demange: ESSEC Business School
Bernard Kouakou: CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique
Eric Soutif: CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique, CEDRIC - Centre d'études et de recherche en informatique et communications - ENSIIE - Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise - CNAM - Conservatoire National des Arts et Métiers [CNAM]

Post-Print from HAL

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: competitivity ratio; On-line algorithm; hereditary property; independent set; propriété héréditaire; ensemble indépendant; algorithme en ligne; rapport de compétitivité (search for similar items in EconPapers)
Date: 2006-05
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-00115615
References: View complete reference list from CitEc
Citations:

Published in 2006

Downloads: (external link)
https://shs.hal.science/halshs-00115615/document (application/pdf)

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:hal:journl:halshs-00115615

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().