Skip to Main content Skip to Navigation
Other publications

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 metadata

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 : Wednesday, January 27, 2021 - 7:16:57 PM
Long-term archiving on: : 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

404

Files downloads

532