Skip to Main content Skip to Navigation

On-line computation and maximum-weighted hereditary subgraph problems

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.
Document type :
Other publications
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://halshs.archives-ouvertes.fr/halshs-00115615
Contributor : Lucie Label <>
Submitted on : Wednesday, November 22, 2006 - 11:42:32 AM
Last modification on : Monday, February 3, 2020 - 3:40:14 PM
Document(s) archivé(s) le : Tuesday, April 6, 2010 - 11:12:08 PM

File

B06034.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : halshs-00115615, version 1

Citation

Marc Demange, Bernard Kouakou, Eric Soutif. On-line computation and maximum-weighted hereditary subgraph problems. 2006. ⟨halshs-00115615⟩

Share

Metrics

Record views

305

Files downloads

410